^ @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)..