CODEWITHSUNDEEP
algorithmdata-structuresbinary-tree
user3259176
user3259176

Reputation:

Count number of nodes within range inside Binary Search Tree in O(LogN)

Given a BST and two integers 'a' and 'b' (a < b), how can we find the number of nodes such that , a < node value < b, in O(log n)?

I know one can easily find the position of a and b in LogN time, but how to count the nodes in between without doing a traversal, which is O(n)?

Upvotes: 6

Views: 11348

Answers (4)

nagendra547
nagendra547

Reputation: 6302

Simple solution:

  • Start checking from the root node
  • If Node falls within range, then increase it by 1 and check in left and right child recursively

  • If Node is not within range, then check the values with range. If range values are less than root, then definitely possible scenarios are left subtree. Else check in right subtree

    Here is the sample code. Hope it clears.

    if (node == null) {
    return 0;
} else if (node.data == x && node.data == y) {
    return 1;
} else if (node.data >= x && node.data <= y) {
    return 1 + nodesWithInRange(node.left, x, y) + nodesWithInRange(node.right, x, y);
} else if (node.data > x && node.data > y) {
    return nodesWithInRange(node.left, x, y);
} else {
    return nodesWithInRange(node.right, x, y);
}

Time Complexity :- O(logn)+ O(K)

K is the number of elements between x and y.

It's not very ideal but good in case you would not like to modify the Binary Tree nodes definition.

Upvotes: 2

displayName
displayName

Reputation: 14389

In each node of your Binary Search Tree, also keep count of the number of values in the tree that are lesser than its value (or, for a different tree design mentioned in the footnote below, the nodes in its left subtree).

Now, first find the node containing the value a. Get the count of values lesser than a which has been stored in this node. This step is Log(n).

Now find the node containing the value b. Get the count of values lesser than b which are stored in this node. This step is also Log(n).

Subtract the two counts and you have the number of nodes between a and b. Total complexity of this search is 2*Log(n) = O(Log(n)).

See this video. The professor explains your question here by using Splay Trees.

Upvotes: 7

Cereal_Killer
Cereal_Killer

Reputation: 324

store the inorder traversal of BST in array( it will be sorted). Searching 'a' and 'b' will take log(n) time and get their index and take the difference. this will give the number of node in range 'a' to 'b'.

space complexity O(n)

Upvotes: 1

FallAndLearn
FallAndLearn

Reputation: 4135

Idea is simple.

  1. Traverse the BST starting from root.
  2. For every node check if it lies in range. If it lies in range then count++. And recur for both of its children.
  3. If current node is smaller than low value of range, then recur for right child, else recur for left child.

Time complexity will be O(height + number of nodes in range)..

For your question that why it is not O(n).

Because we are not traversing the whole tree that is the number of nodes in the tree. We are just traversing the required subtree according to the parent's data.

Pseudocode

int findCountInRange(Node root, int a, int b){

    if(root==null)
       return 0;
    if(root->data <= a && root->data >= b)
         return 1 + findCountInRange(root->left, a, b)+findCountInRange(root->right, a, b); 
    else if(root->data < low)
         return findCountInRange(root->right, a, b);
    else 
         return findCountInRange(root->left, a, b);

}

Upvotes: -1

Related Questions