Suppose there is a balanced binary search tree with $ n$ nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node.

Now, given two elements $ a$ and $ b$ , such that $ a < b$ , we want to find the number of elements $ x$ in the tree that lie between $ a$ and $ b$ , that is, $ a \leq x \leq b$ . This can be done with (choose the best solution).

$ O(\log n)$ comparisons and $ O(\log n)$ additions. $ O(\log n)$ comparisons but no further additions. $ O \left (\sqrt{n} \right )$ comparisons but $ O(\log n)$ additions. $ O(\log n)$ comparisons but a constant number of additions. $ O(n)$ comparisons and $ O(n)$ additions, using depth-first- search.

I got this ans Find Number of elements X in the Tree that lie between a and b but still not able to got , if only O(log n) comparison sufficient to find number of nodes??

Say if our answer is whole tree, then how only log n comparison can do that with log n addition?? We need n addition .

right??