Count number of nodes within a certain range in AVL Tree

Question

Is there a way to find the number (count only) of nodes between 2 given nodes in a balanced binary search tree using their ranks in < O(log n) time?

We can assume that we already store each Node's rank (or height) dynamically as the Node class' member variable. So, we can access it directly.

Answer 1

Yes, using lowest common ancestor queries it is possible to count the nodes in between in constant time. It requires a one time preprocessing of the tree in linear time.

If you know the rank of the lowest common ancestor of two nodes, then you can compute how many nodes are between a node and the ancestor by subtracting the rank of the ancestor from the rank of the child node.

nodes_between = a.rank + b.rank - 2*(lowest_common_ancestor(a, b).rank) + 1

The above will return the length of the path between nodes a and b including the two end point. The + 1 is for the lowest common ancestor itself. Finding the lowest_common_ancestor can be done in constant time and the calculation is constant time.