# Binary search trees: multiple Successor() calls

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)?

• 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?) – David Richerby May 8 '17 at 14:10
• @DavidRicherby. The title said the tree was a BST. At least "successor" makes some sense for such critters. – Rick Decker May 8 '17 at 15:10
• @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. – David Richerby May 8 '17 at 16:56
• 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. – D.W. May 8 '17 at 22:47

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).