title: Printing Successor and Predecessor in a BST
body: <p>My problem is as follows:</p>
  
  <p>I have a binary search tree with keys: <code>a1&lt;a2&lt;...&lt;an</code>, the problem is to print all the (a_i, a_i+1) pairs in the tree (where i={1,2,3,...}) using a recursive algorithm in O(n) time without any global variable and using O(1) extra space. An example:
  Let the keys be: 1,2, ..., 5
  Pairs that will be printed: (1,2) (2,3) (3, 4) (4, 5)</p>
  
  <p>So you can't do inorder traversal in the tree and find the successor/predecessor for each node. Because that would take O(nh) time and if the tree is balanced, it will be O(nlgn) for the whole tree. </p>