Populate Inorder successor of all nodes

The problem, simply

Every spot in the tree has the usual left and right arrows, and one more empty arrow called next. Fill in next so it points to the spot that comes right after this one in sorted order (its inorder successor). The biggest spot's next stays null.

When you are done, you can start at the smallest spot and follow next arrows to visit every number in sorted order, like a chain.

In the classic version the tree is any binary tree and "sorted order" means the left, me, right reading order. For a BST, that order is exactly smallest to biggest.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write every spot into a list in left, me, right order. Then walk the list and point each spot to the one after it.

1. Visit left side, the spot, right side, and add each spot to a list.
2. For i from 0 to the second last, set list[i].next = list[i + 1].
3. The last one's next is null.

import java.util.*;

class Solution {
    public void populateNext(Node root) {
        List<Node> order = new ArrayList<>();
        inorder(root, order);
        for (int i = 0; i + 1 < order.size(); i++) {
            order.get(i).next = order.get(i + 1);   // point to the one after me
        }
        if (!order.isEmpty()) order.get(order.size() - 1).next = null;
    }

    private void inorder(Node node, List<Node> order) {
        if (node == null) return;
        inorder(node.left, order);
        order.add(node);
        inorder(node.right, order);
    }
}

How long it takes: every spot twice, O(n). Extra room: the list of all spots, O(n).

Way 2: the clever way

Visit in the opposite order: right side, the spot, left side. That reads the numbers from biggest to smallest. Keep one finger, prev, on the spot you visited last.

1. Start with prev = null.
2. Visit the right side first.
3. At the spot: set spot.next = prev, then move prev to this spot.
4. Visit the left side.

The spot you visited just before is the next bigger one, which is exactly the successor. The chain grows from its end back to its start.

class Solution {
    private Node prev;                     // the spot visited just before

    public void populateNext(Node root) {
        prev = null;
        fill(root);
    }

    private void fill(Node node) {
        if (node == null) return;
        fill(node.right);                  // bigger numbers first
        node.next = prev;                  // the last one seen is my successor
        prev = node;
        fill(node.left);                   // then smaller numbers
    }
}

How long it takes: every spot once, O(n). Extra room: no list, only the recursion, O(h).

Another way: Morris walk with no extra room

To get O(1) extra room, walk left, me, right without a stack. Before going down to the left side, find the biggest spot on that side and point its right arrow back up to the current spot, like leaving a rope to climb back. When you come back by the rope, remove it. In this forward order, link prev.next = curr.

class Solution {
    public void populateNext(Node root) {
        Node curr = root, prev = null;
        while (curr != null) {
            if (curr.left == null) {
                if (prev != null) prev.next = curr;   // visit
                prev = curr;
                curr = curr.right;
            } else {
                Node rope = curr.left;
                while (rope.right != null && rope.right != curr) rope = rope.right;
                if (rope.right == null) {            // first time here: tie the rope
                    rope.right = curr;
                    curr = curr.left;
                } else {                             // came back by the rope: untie it
                    rope.right = null;
                    if (prev != null) prev.next = curr;
                    prev = curr;
                    curr = curr.right;
                }
            }
        }
        if (prev != null) prev.next = null;
    }
}

Still O(n) time (each rope is walked a constant number of times), and O(1) extra room. The tree is put back exactly as it was.

Watch out for

• Visiting left first while setting node.next = prev. That points each spot at its predecessor, the wrong way round. Left-first order needs prev.next = node instead.
• Forgetting to reset prev between calls.
• The biggest spot's next must be null. Both ways do this for free.

What interviewers ask next

• Populate the predecessor arrow instead. Visit left, me, right, and set node.prev = prev.
• Connect each spot to the spot on its right in the same row (LeetCode 116 and 117). That is a different "next": use the row by row walk, or reuse the already linked row above to link the row below in O(1) room.
• Turn the BST into a sorted doubly linked list in place. Same walk, but reuse left as "previous" and right as "next".
• Why does the Morris walk not break the tree? Every rope is tied once and untied once before the walk leaves that part.

Remember this

Grown-up words: the next bigger kid is the inorder successor, right, me, left is a reverse inorder traversal, the finger on the last visited spot is a prev pointer, and the rope trick is a Morris traversal using threaded pointers.