In Order Successor in Binary Search Tree

Question

Given a node in a BST, how does one find the next higher key?

Answer 1

The general way depends on whether you have a parent link in your nodes or not.

If you store the parent link

Then you pick:

1. The leftmost child of the right child, if your current node has a right child. If the right child has no left child, the right child is your inorder successor.
2. Navigate up the parent ancestor nodes, and when you find a parent whose left child is the node you're currently at, the parent is the inorder successor of your original node.

If you have right child, do this approach (case 1 above):

If you don't have a right child, do this approach (case 2 above):

If you don't store the parent link

Then you need to run a complete scan of the tree, keeping track of the nodes, usually with a stack, so that you have the information necessary to basically do the same as the first method that relied on the parent link.

Answer 2

Python code to the Lasse's answer:

def findNext(node):
  # Case 1
  if node.right != None:
    node = node.right:
    while node.left:
      node = node.left
    return node

  # Case 2
  parent = node.parent
  while parent != None:
    if parent.left == node:
      break
    node = parent
    parent = node.parent
  return parent

Answer 3

Here's an implementation without the need for parent links or intermediate structures (like a stack). This in-order successor function is a bit different to what most might be looking for since it operates on the key as opposed to the node. Also, it will find a successor of a key even if it is not present in the tree. Not too hard to change if you needed to, however.

public class Node<T extends Comparable<T>> {

private T data;
private Node<T> left;
private Node<T> right;

public Node(T data, Node<T> left, Node<T> right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

/*
 * Returns the left-most node of the current node. If there is no left child, the current node is the left-most.
 */
private Node<T> getLeftMost() {
    Node<T> curr = this;
    while(curr.left != null) curr = curr.left;
    return curr;
}

/*
 * Returns the right-most node of the current node. If there is no right child, the current node is the right-most.
 */
private Node<T> getRightMost() {
    Node<T> curr = this;
    while(curr.right != null) curr = curr.right;
    return curr;
}

/**
 * Returns the in-order successor of the specified key.
 * @param key The key.
 * @return
 */
public T getSuccessor(T key) {
    Node<T> curr = this;
    T successor = null;
    while(curr != null) {
        // If this.data < key, search to the right.
        if(curr.data.compareTo(key) < 0 && curr.right != null) {
            curr = curr.right;
        }
        // If this.data > key, search to the left.
        else if(curr.data.compareTo(key) > 0) { 
            // If the right-most on the left side has bigger than the key, search left.
            if(curr.left != null && curr.left.getRightMost().data.compareTo(key) > 0) {
                curr = curr.left;
            }
            // If there's no left, or the right-most on the left branch is smaller than the key, we're at the successor.
            else {
                successor = curr.data;
                curr = null;
            }
        }
        // this.data == key...
        else {
            // so get the right-most data.
            if(curr.right != null) {
                successor = curr.right.getLeftMost().data;
            }
            // there is no successor.
            else {
                successor = null;
            }
            curr = null;
        }
    }
    return successor;
}

public static void main(String[] args) {
    Node<Integer> one, three, five, seven, two, six, four;
    one = new Node<Integer>(Integer.valueOf(1), null, null);
    three = new Node<Integer>(Integer.valueOf(3), null, null);
    five = new Node<Integer>(Integer.valueOf(5), null, null);
    seven = new Node<Integer>(Integer.valueOf(7), null, null);
    two = new Node<Integer>(Integer.valueOf(2), one, three);
    six = new Node<Integer>(Integer.valueOf(6), five, seven);
    four = new Node<Integer>(Integer.valueOf(4), two, six);
    Node<Integer> head = four;
    for(int i = 0; i <= 7; i++) {
        System.out.println(head.getSuccessor(i));
    }
}
}