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.

Consider a startng node \(a\) and an ending node \(b\) where \(b\) is \(a\)’s \(k\)ᵗʰ successor. As discussed in Exercise 12.2-7 each of the \(k\) nodes separating \(a\) and \(b\) will be visited at most twice. Any node that is not between \(a\) and \(b\) will be visited at most once, and there cannot be more than \(h\) such nodes. Thus the runtime is bounded by \(3k+2h = O(k + h)\).