Prove the efficiency of repeated calls to successor() in binary trees?

Question

I need a hint for this exercise from the CLRS Algorithms book:

Prove that no matter what node we start at in a height-h binary search tree, k successive calls to Tree-Successor take O(k+h) time.

Answer 1

• Let x be the starting node and z be the ending node after k successive calls to TREE-SUCCESSOR.
• Let p be the simple path between x and z inclusive.
• Let y be the common ancestor of x and z that p visits.
• The length of p is at most 2h, which is O(h).
• Let output be the elements that their values are between x.key and z.key inclusive.
• The size of output is O(k).
• In the execution of k successive calls to TREE-SUCCESSOR, the nodes that are in p are visited, and besides the nodes x, y and z, if a sub tree of a node in p is visited then all its elements are in output.
• So the running time is O(h+k).

Answer 2

Hint: work out a small example, observe the result, try to extrapolate the reason.

To get started, here are some things to consider.

Start at a certain node, k succesive calls to Tree-Succcesor consititutes a partial tree walk. How many (at least and at most) nodes does this walk visit? (Hint: Think about key(x)). Keep in mind that an edge is visited at most twice (why?).

Final hint: The result is O(2h+k).