Find the successor in a BST without using parent pointer

Question

The successor of an element in a BST is the element's successor in the sorted order determined by the inorder traversal. Finding the successor when each node has a pointer to its parent node is presented in CLRS's algorithm textbook. (Intro to algorithm by MIT press). Now I am thinking another question, can we find the successor without using the pointer to the parent node. Sometimes our tree node does not have this pointer. I struggled a couple of hours but cannot write the correct code.

The idea in CLRS's book of finding the successor is, if the right subtree of node x is nonempty, the successor of x is the min element in the right subtree. Otherwise, the successor is the lowest ancestor of x whose left child is also an ancestor of x.( Note a node is an ancestor of itself).

Answer 1

If you don't have access to the pointer to the parent node then you need to know who the father is. If you don't know it, how could you go up in the tree ?

Answer 2

Well, if you have a pointer to the node, then you find the value and do a search in the tree for that value. You will get a path to the node. Now it reduces to an already solved problem :-)

Answer 3

This should work:

TREE-SUCCESSOR(T, x)
  if right[x] != NIL
    then return TREE-MINIMUM(right[x])
  return FIND-TREE-SUCCESSOR(root[T], x, NIL)

FIND-TREE-SUCCESSOR(y, x, c)
  if y = x
    then return c
  if key[x] < key[y]
    then return FIND-TREE-SUCCESSOR(left[y], x, y)
    then return FIND-TREE-SUCCESSOR(right[y], x, c)

FIND-TREE-SUCCESSOR keeps in c (of candidate) the last node in which we turned left.