Here is an example 😊
$L =25 , H = 35$
Inorder: $10,15,20,\underset{L}{\boxed{25}},26,27,28,30,31,32,33,34,\underset{H}{\boxed{35}},36,39,42$
- Find $L$ and $H \rightarrow O(\log n)$ time.
- Traverse '$m$' elements between '$L$' and '$H$' $\rightarrow O(m)$ [Traversal algorithm]
Total $\rightarrow O(m + \log n) $
$\qquad a= 0,b=1,c=1,d=0$
$\qquad 10 + 100 = 110$ Answer
Traversal Algorithm:
- Find $L$ using Binary search and keep $H>node> L$ encountered in the search in a stack.
- After finding $L,$ add it to stack as well & initialize $sum = 0$
- Now, for all nodes in the stack, do an inorder traversal starting from their right node and adding the node value to sum. If it is found than stop the algorithm.
- Node (1)
- No Right child; Sum = Sum + Node value $= 0 + 25 = 25.$
- Node (2)
- Inorder Traversal from Right Child $\rightarrow 24,28$
- Sum = sum + inorder Traversal + Node Value $= (25 + 27 + 28) + 26$
- Node (3)
- Inorder Traversal From Right Child $\rightarrow 31,32,33,34,\overset{H}{\bf{35}}\overset{\to \text{Stop Inorder Traversal}}{}$
- Sum = Sum + Inorder Traversal + Node value
- $\qquad = 25 + 26 + 24 + 28 + (31 + 32 + 33 + 34 + 35) + 30$
- $\qquad = 25 + 26 + 24 + 28 + 30 + 31 + 32 + 33 + 34 + 35$ Answer
EDIT :
- In Step 1, we need to find only $L$ and not $H.$
- In Traversal Algo: Find $L$ using Binary Search and Keep, L< Nodes< H, encountered in the search in the stack.