Show that, given a tree node a, the time complexity of calling k times to Successor() is $O(k+h)$, where $h$ is the tree height.

I understand that we're passing by at least $k$ nodes, but how I can prove that in all these calls we do not iterate over the tree height (at most)?

  • 2
    $\begingroup$ The answer will clearly depend on what nodes successor() is called on, so I don't see how this can be answered. (It also depends on what successor() actually does. What even is the successor of a node in a tree?) $\endgroup$ – David Richerby May 8 '17 at 14:10
  • $\begingroup$ @DavidRicherby. The title said the tree was a BST. At least "successor" makes some sense for such critters. $\endgroup$ – Rick Decker May 8 '17 at 15:10
  • $\begingroup$ @RickDecker Fair point. This is part of the reason why people should include all the information in the question rather than requiring people to read other stuff. $\endgroup$ – David Richerby May 8 '17 at 16:56
  • 1
    $\begingroup$ 1. You haven't defined Successor(). Please edit your question to make it self-contained. If Successor() is a subroutine, please define/specify what that does and how. 2. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. May 8 '17 at 22:47

Here are a few hints that could help you:

  1. Consider a complete binary tree, and suppose that you run the successor operation, starting with the left-most leaf. The number of edges you go up and down at each step are 2, 4, 2, 6, 2, 4, 2, 8 and so on. You can use an explicit formula to show that the average number of steps in any prefix is always at most 4.

  2. If you start this sequence in the middle, then there could be a "bump", and this corresponds to the appearance of $h$ in your formula. With some effort, you can show that the total sum of any consecutive subsequence of the above sequence is $O(h+k)$, where $k$ is the length of the subsequence, and $h$ is the maximal number appearing (which is double the height).

  3. A general binary search tree need not be complete, but in some sense a complete binary tree is the "worst case", though you'd have to argue this formally somehow.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.