# Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder

I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.

• Draw a tree with 12 nodes. Using your fingers, find the 7th node. Is it obvious now? If not, what is the problem? – gnasher729 Mar 5 '18 at 16:35
• Hi @gnasher729, my problem that i need to proof it by math or other way and not just check by example and see the it's obvious. – ChaosPredictor Mar 5 '18 at 16:39
• Do the example then you’ll figure out the proof. Have you tried it? If not, why not? – gnasher729 Mar 5 '18 at 18:43
• Indeed. Write down the algorithm. Analyse it. – Raphael Mar 5 '18 at 18:53
• The algorithm that i know to inorder is a recursive, I know how to proof the total time. $T(n)=2T(n/2)+1$ the solution of it is $T(n)=n$, but it isn't solution till the $i$ object. I thought about 4 directions that Next can go: downLeft & upRight - cheap (this require only 1 operation to perform) downRight & upLeft - expensive (this can require $k$ operations to perform), but this expensive actions done after $k$ cheap actions. In conclusion I can't say that I like this solution. – ChaosPredictor Mar 5 '18 at 19:57