# Count nodes in a BST that lies within a given range | Techie Delight

#### Bydinesh

Apr 30, 2022

// BST node

class Node

{

int data;

Node left, right;

Node(int data)

{

this.data = data;

this.left = this.right = null;

}

}

class Main

{

// Recursive function to insert a given key into a BST

public static Node insert(Node root, int key)

{

if (root == null) {

return new Node(key);

}

if (key < root.data) {

root.left = insert(root.left, key);

}

else {

root.right = insert(root.right, key);

}

return root;

}

// Function to count nodes in the BST that lie within a given range

public static int countNodes(Node root, int low, int high)

{

// base case

if (root == null) {

return 0;

}

// if the current node lies within the current range, increment the count

// and recur for both left and right subtree

if (root.data >= low && root.data <= high)

{

return 1 + countNodes(root.left, low, high) +

countNodes(root.right, low, high);

}

// recur for the left subtree if range lies on its left subtree

if (root.data > high) {

return countNodes(root.left, low, high);

}

// recur for the right subtree if the range lies on its right subtree

if (root.data < low) {

return countNodes(root.right, low, high);

}

return 0;

}

public static void main(String[] args)

{

// input range

int low = 12, high = 20;

int[] keys = { 15, 25, 20, 22, 30, 18, 10, 8, 9, 12, 6 };

// construct BST from the above keys

Node root = null;

for (int key: keys) {

root = insert(root, key);

}

System.out.println(“The total number of nodes is “ +

countNodes(root, low, high));

}

}

Source