Count BST nodes that lie in a given range

Count BST nodes that lie in a given range

  April 21, 2020    

---

Problem :

Given a Binary Search Tree (BST) and a range low-high(inclusive), count the number of nodes in the BST that lie in the given range.

Solution :

As this tree is BST , it means that left subtree will have value less than root and right sub tree will have value greater than root.

It means if root is less than lower range then only right sub Tree can have node which lies in the range and if root is greater than high range then only left sub Tree can have node which lies in the range.

Code:  

public static int getCountOfNode(Node root,int l, int h)
{
    if(root == null) return 0;
    if(root.data<l)
    return getCountOfNode(root.right,l,h);
    else if(root.data>h)
    return getCountOfNode(root.left,l,h);
    else
    return 1+getCountOfNode(root.left,l,h)+getCountOfNode(root.right,l,h);
}