^ @srestha..why to count all nodes... just count the node which are there in the path of P to a and P to b...and use formula accordingly.. which can be done in O(log n).. right ??

And here in your example ... @arjun sir's formula is working well but .. try to use this formula for the example I hv posted..

For your 1st example , when both the node are in the same path from P any leaf..b ( like 12 and 17 are in the same path from root(10) to leaf (20)..

then, do following steps -

Calculate N(Right(a) = 3 // node - 16 , 17 , 20 ....O(log n) time

calculate N(Right(b)) = 1 // node - 20 ...O( log n) time.

So, N ( a< N < b) = N(Right(a)) - N( Right(b) - 1 = 3 - 1 -1 = 1 // node 16 only.

**total addition - O(1)**

For your second case example -

Do following steps -

1. First find common ancestor of node ...here 16 ... // O(log n) time

2. take count variable = 0.

3. do add all right subent nodes from P to a ..

here - count =count + N(Right ( 14 )) + 1 (counting node 14 as well) =0+ 1 + 1 =2.

count = count + N(Right (12 )) = 2 + 1 = 3.

4. do add all left subent nodes from P to b ..

here - count = count + N(left (17)) = 3 + 0.

5. finaly, total N(a<N<b) = count + 1 ( counting node 16 ..).

Again , total addition -- O(log n)..