Time complexity of finding k successors in BST

Question

Given a binary search tree (BST) of height h, it would take O(k+h) time to apply the BST InOrder Successor algorithm k times in succession, starting in any node, applying each next call on the node that was returned by the previous call.

Pseudo code:

get_kth_successor(node):
    for times = 1 to k:
        node = successor(node)
    return node

How can I prove this time complexity?

In particular, I am trying to establish a relation between k and the number of nodes visited, but can't find any pattern here.

Answer 1

Take the following truths concerning a successor(s) traversal:

1. You can traverse a branch not more than two times: downward and upward.

2. Every double visit of a branch corresponds to finding at least one more successor: when you backtrack via a branch upwards, you will have visited at least one successor more than at the time you passed that same branch the first time, in the downward direction.

3. The number of branches you will traverse only once cannot be more than 2h. This worst case happens when you start at a leaf in the bottom-left side of the tree and must go all the way up to the root (a successor) and then down again to a bottom-leaf to find the successor of the root. But if you need more successors after that, you will have to visit some of these branches again (in backtracking) before you can traverse other branches for the first time. So the total number of branches you traverse only once cannot increase above 2h.

So, to find k successors you will at the most traverse k branches twice (downward and upward, cf. point 2) and 2h branches once (point 3), which comes down to a worst case branch-traversal-count of 2k+2h which is O(h+k).