algorithmdata-structuresbinary-tree

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)?

Solution

  • 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)).