Find inorder successor and inorder predecessor in a BST

The problem, simply

You get a binary search tree (BST) and a key. Imagine writing every number in the tree in a sorted row. The number just before the key in that row is the predecessor. The number just after it is the successor.

Find both. If one does not exist (the key is the smallest, or the biggest), say null for it. A good answer also works when the key itself is not in the tree: then the predecessor is the biggest number smaller than the key, and the successor is the smallest number bigger than the key.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write out the whole sorted row, then look left and right of the key.

1. Walk the tree left side, then the spot, then the right side. This writes the numbers in sorted order.
2. Find the key in the row.
3. The one before it is the predecessor, the one after is the successor.

import java.util.*;

class Solution {
    public Integer[] predSucc(TreeNode root, int key) {
        List<Integer> row = new ArrayList<>();
        inorder(root, row);
        Integer pred = null, succ = null;
        for (int x : row) {
            if (x < key) pred = x;                     // the last one smaller than key
            if (x > key && succ == null) succ = x;     // the first one bigger than key
        }
        return new Integer[] { pred, succ };
    }

    private void inorder(TreeNode node, List<Integer> row) {
        if (node == null) return;
        inorder(node.left, row);
        row.add(node.val);
        inorder(node.right, row);
    }
}

How long it takes: we write out every number, O(n). Extra room: the row, O(n). Using "last smaller" and "first bigger" instead of looking up the key's position also handles a key that is not in the tree.

Way 2: the clever way

Walk down from the top like a normal search, and keep two notes, pred and succ.

1. If the key is smaller than the current spot, this spot is bigger than the key, so it could be the successor. Write succ = curr and go left (to find something closer).
2. If the key is bigger, this spot could be the predecessor. Write pred = curr and go right.
3. If you found the key: the biggest spot on its left side (go left once, then right as far as you can) is a closer predecessor. The smallest spot on its right side (go right once, then left as far as you can) is a closer successor.

Why the latest note is the closest: each time you go left from a spot, every spot after that is smaller than it, so any later succ note beats the earlier one.

class Solution {
    public TreeNode[] predSucc(TreeNode root, int key) {
        TreeNode pred = null, succ = null, curr = root;
        while (curr != null) {
            if (key < curr.val) {
                succ = curr;               // bigger than key: a successor so far
                curr = curr.left;
            } else if (key > curr.val) {
                pred = curr;               // smaller than key: a predecessor so far
                curr = curr.right;
            } else {
                if (curr.left != null) {   // biggest on the left side
                    TreeNode t = curr.left;
                    while (t.right != null) t = t.right;
                    pred = t;
                }
                if (curr.right != null) {  // smallest on the right side
                    TreeNode t = curr.right;
                    while (t.left != null) t = t.left;
                    succ = t;
                }
                break;
            }
        }
        return new TreeNode[] { pred, succ };
    }
}

How long it takes: one road down, plus at most one short road below the key, all within the height, O(h). Extra room: a few fingers, O(1).

Watch out for

• When the key is missing, the walk ends at null and the notes are still right. Do not return null for both.
• Mixing up which note to update. Going left means the spot is bigger: that is succ. Going right means the spot is smaller: that is pred.
• If the problem gives you parent pointers and no root, the "no right side" case climbs up: keep going to the parent until you arrive from a left child.

What interviewers ask next

• Only the successor, given the node p (LeetCode 285). Walk from the top: if p.val < curr.val, note curr and go left, otherwise go right. Equal goes right, so p itself is never chosen. Six lines.
• Successor when nodes have parent pointers and you are not given the root (LeetCode 510). If p has a right side, take its leftmost. Else climb while you are a right child. The parent you reach is the answer.
• Iterate over a BST in sorted order with next() and hasNext() (BST iterator). Keep a stack of the left road. next() pops, then pushes the left road of the popped spot's right child. Average O(1) per call, O(h) room.
• Floor and ceiling of a key that may be missing. Exactly pred/succ from this walk, but with <= and >= so an exact match counts.

Remember this

Grown-up words: the sorted row is the inorder traversal, the "before" neighbor is the inorder predecessor, the "after" neighbor is the inorder successor, the biggest on the left side is the rightmost node of the left subtree, and floor and ceiling are the predecessor and successor when an exact match is allowed.