Find the successor without using parent pointer [duplicate]

Question

This question already has an answer here:

• In Order Successor in Binary Search Tree 16 answers

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 (Introduction to Algorithms by MIT press).

The idea to find the successor here is - if the right subtree of node x is nonempty, the successor of x is the minimum element in the right subtree. Otherwise, the successor is the lowest ancestor of x whose left child is also an ancestor of x (assuming a node is an ancestor of itself).

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.

Answer 1

This should work:

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

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

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

Answer 2

Inspired by Sheldon's solution ,this is the non-recursive version of the solution.

if (right[x]  != NIL)
    return min(right[x]);
else
{
    candidate = NIL;
    y = root; 
    while  (y!= x) // y is used as a probe

        if (key[x] < key[y])
            {
            candidate = y;
            y = y ->left;

             }
        else
            y = y->right;
}
return candidate;

If candidate == NIL, x is the max in the tree and does not have a successor.

Answer 3

I found an elegant solution for in-order successor without parent pointer here -> http://www.geeksforgeeks.org/archives/9999

Idea is

1.If the node has right sub-tree, then its successor is the least element in the right sub-tree

1. If the node's right sub-tree is empty, then its successor is one of its ancestors, which can be found top-down without parent pointer, with the following algorithm:

let initially current_node be root, succ_node = null;

case1: If the search element is less than current_node, then the current element is a potential successor - place succ_node at the current_node and move the current_node to its left node(because the search element is in the left subtree)

case2: If the search element is greater then current_node, its not a potential successor (How can a lesser element be the successor?). So no need to place the succ_node here, but move the current_node to right.

keep repeating the process until you reach null or the element itself and return the succ_node.

Answer 4

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 5

A recursive Java solution could look the following way:

public Integer successor(Integer value) {
    Node n = succ(root, value, null);
    if (null != n) {
       return n.value;
    }
    return null;
}

private Node succ(Node n, Integer x, Node p) {
    if (null == n) {
        return null;
    }

    if (x < n.value) {
        return succ(n.left, x, n);
    } else if (x > n.value) {
        return succ(n.right, x, p);
    }
    if (null != n.right) {
        return min(n.right);
    }
    return p;
}

As a client we simply pass in the value of the node from which we want to know the successor. Then we start searching from the root until we found the value we were looking for. Now there are two cases:

1. If the current node has a right child, then the successor the smallest element in the current node's right subtree
2. Otherwise, it was the node p (parent pointer), which was only updated when we went left within the tree