Recently, I came across a question about finding sum of all values in range $[low, high]$ in BST $T$.
Then I formulated following algorithm to carry out that task:
- We do inorder traversal of BST ($sum = 0$ in start)
- But whenever we encounter any node having value strictly less than $low$ than we don't visit it's left subtree. We only traverse it's right subtree recursively in same manner.
- In same manner if we find any node having value strictly greater than $high$ than we don't traverse it's right subtree.
- If value of node falls in given range then we increment $sum$ by 1.
I think this algorithm correctly solve above problem in time complexity $O(m+lg(n))$ where $m$ is number of nodes having value in given range.
My reasoning for that time complexity is that we traverse at most $O(lg(n))$ nodes(This statement I'm not able to prove) which don't get added and we traverse $m$ nodes that gets added into $sum$. Which gives above time complexity.
At least any hint regarding how to prove this time complexity would be great.