title: Prove that k successive calls to TREE-SUCCESSOR take O(k + h) time
body: <p>This question has been around for while, but I still have a question please. I will discuss the following solution.</p>
  <p><strong>Question</strong>: Prove that no matter what node we start at in a height-<code>h</code> binary search tree, <code>k</code> successive calls to TREE-SUCCESSOR take <code>O(k + h)</code> time.</p>
  <p>Given tree successor algorithm below, that given an x, it will find it's left-most node of right-subtree of <code>x</code>:</p>
  <p><a href="https://i.stack.imgur.com/d8o7c.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/d8o7c.png" alt="enter image description here" /></a></p>
  <p><strong>Assumptions</strong>: Assuming that the worst-case running time of <code>TREE-SUCCESSOR()</code> is O(h), where h is the height of binary search tree and the tree will not be changed between successive calls of the method. The worst case happens when next successor is a leaf at depth h.</p>
  <p>You need to call once the method to get the next successor and you need <code>O(h)</code> time for that. Once when you have the next successor you simply can store it and for every other call, you can return it in <code>O(1)</code>. Since, you have <code>k−1</code> remaining calls, the running time is <code>O(k)</code>. Combining with the above, you have that the total running time is <code>O(h)+O(k)=O(k+h)</code>.</p>
  <p><strong>Question</strong>: I am not sure by the last statement about how we got running time O(k) please? I assume k successive calls to <code>TREE-SUCCESSOR()</code> means that we are calling it k times on probably same or different nodes? If that is the case, we know that worst time for <code>TREE-SUCCESSOR </code> is <code>O(h)</code>, so how we got a total time of <code>O(h+k)</code> please? I can see that if we call <code>TREE-SUCCESSOR()</code> <code>k</code> times, then we should get worst-case of <code>O(kh)</code>.</p>
  <p><strong>Edit</strong>: I would assume probably that <code>k</code> succissive calls to <code>TREE-SUCCESSOR()</code> means: <code>TREE-SUCCESSOR()+⋯+TREE-SUCCESSOR(): k times</code>?</p>