# Count nodes in a BST that lies within a given range // BST node

class Node

int knowledge;

Node left, proper;

Node(int knowledge)

this.knowledge = knowledge;

this.left = this.proper = null;

class Major

// Recursive perform to insert a given key right into a BST

public static Node insert(Node root, int key)

if (root == null)

return new Node(key);

if (key < root.knowledge)

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

else

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

return root;

// Operate to rely nodes within the BST that lie inside a given vary

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

// base case

if (root == null)

return 0;

// if the present node lies throughout the present vary, increment the rely

// and recur for each left and proper subtree

if (root.knowledge >= low && root.knowledge <= excessive)

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

countNodes(root.proper, low, excessive);

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

if (root.knowledge > excessive)

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

// recur for the best subtree if the vary lies on its proper subtree

if (root.knowledge < low)

return countNodes(root.proper, low, excessive);

return 0;

public static void essential(String[] args)

// enter vary

int low = 12, excessive = 20;

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

// assemble BST from the above keys

Node root = null;

for (int key: keys)

root = insert(root, key);

System.out.println(“The overall variety of nodes is “ +

countNodes(root, low, excessive));