Tuesday, October 11, 2022

Count BST nodes that lie in a given range

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

  • The values smaller than root go to the left side
  • The values greater and equal to the root go to the right side

Example 1:

Input:
      10
     /  \
    5    50
   /    /  \
  1    40  100
l = 5, h = 45
Output: 3
Explanation: 5 10 40 are the node in the
range

Example 2:

Input:
     5
    /  \
   4    6
  /      \
 3        7
l = 2, h = 8
Output: 5
Explanation: All the nodes are in the
given range.

Your Task:
This is a function problem. You don't have to take input. You are required to complete the function getCountOfNode() that takes root, l ,h as parameters and returns the count.

My Answer:

    int getCount(Node root, int l, int h)
    {
        int count = 0;
        ArrayList<Integer> list = new ArrayList<>();
        list = getNodeData(root, list);
        Collections.sort(list);
        for( Integer number : list) {
            if ( number >= l && number <= h ) count = count + 1;
        }
        
        return count;
    }
    
    public ArrayList<Integer> getNodeData(Node node, ArrayList<Integer> list) {
        if( node == null ) return list;
        else {
            list.add(node.data);
            list = getNodeData(node.left, list);
            list = getNodeData(node.right, list);
            return list;
        }
    }

No comments:

Post a Comment

Search in a matrix

  Problem: Given a matrix  mat [][] of size  N  x  M , where every row and column is sorted in increasing order, and a number  X  is given. ...