My problem is as follows:
I have a binary search tree with keys: a1<a2<...<an
, 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)
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.
Although you are right that finding an in-order successor or predecessor might take O(h) time, it turns out that if you start at the smallest value in a BST and repeatedly find its successor, the total amount of work done ends up coming out to O(n) regardless of the shape of the tree.
On intuition for this is to think about how many times you traverse each edge in the tree when iteratively doing successor lookups. Specifically, you will visit every edge in the tree exactly twice: once when you descend into the subtree, and once when you walk up out of it having visited every node in that subtree. Since an n-node tree has O(n) edges, this takes time O(n) to complete.
If you're skeptical about this, try writing a simple program to verify it. I remember not believing this result when I first heard it until I wrote a program to confirm it. :-)
In pseudocode, the logic would look like this:
Hope this helps!