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.

  • 1
    $\begingroup$ Draw a tree with 12 nodes. Using your fingers, find the 7th node. Is it obvious now? If not, what is the problem? $\endgroup$ – gnasher729 Mar 5 '18 at 16:35
  • $\begingroup$ 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. $\endgroup$ – ChaosPredictor Mar 5 '18 at 16:39
  • 1
    $\begingroup$ Do the example then you’ll figure out the proof. Have you tried it? If not, why not? $\endgroup$ – gnasher729 Mar 5 '18 at 18:43
  • $\begingroup$ Indeed. Write down the algorithm. Analyse it. $\endgroup$ – Raphael Mar 5 '18 at 18:53
  • $\begingroup$ 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. $\endgroup$ – ChaosPredictor Mar 5 '18 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.