Flatten BST to sorted list

The problem, simply

You get a binary search tree (BST). Turn it into a sorted chain using the same spots: every spot's left must become null, and its right must point to the next bigger number. Give back the smallest spot, which is the start of the chain.

Do not create new spots. Only change arrows.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write the spots down in order, then hook them up.

1. Visit left side, me, right side and add each spot to a list.
2. For each spot in the list: set left = null and right = the next spot in the list (null for the last one).
3. Return the first spot.

import java.util.*;

class Solution {
    public TreeNode flatten(TreeNode root) {
        List<TreeNode> order = new ArrayList<>();
        inorder(root, order);
        for (int i = 0; i < order.size(); i++) {
            TreeNode node = order.get(i);
            node.left = null;
            node.right = (i + 1 < order.size()) ? order.get(i + 1) : null;
        }
        return order.isEmpty() ? null : order.get(0);
    }

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

How long it takes: two passes, O(n). Extra room: the list of all spots, O(n).

Way 2: the clever way

Hook as you go, with one finger on the end of the chain.

1. Make a dummy spot. The finger tail starts on it. The chain will hang from dummy.right.
2. Visit the spots left side, me, right side.
3. At each spot: tail.right = spot, spot.left = null, then tail = spot.
4. Return dummy.right.

Why it is safe to cut spot.left: when we reach a spot, its whole left side has already been visited and hooked into the chain. Its right is still read by the recursion before anyone overwrites it, because a spot's right is only changed when the next spot is hooked, and the next spot is inside that right side or above it.

class Solution {
    private TreeNode tail;                     // the last spot in the line

    public TreeNode flatten(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        tail = dummy;
        walk(root);
        return dummy.right;
    }

    private void walk(TreeNode node) {
        if (node == null) return;
        walk(node.left);                       // everything smaller joins first
        node.left = null;                      // safe: the left side is already in line
        tail.right = node;                     // join the end of the line
        tail = node;
        walk(node.right);                      // then everything bigger
    }
}

How long it takes: every spot once, O(n). Extra room: no list, only the recursion, O(h). The last spot's right is already null (it was the biggest, with no right side), so the line ends properly.

Watch out for

• Forgetting node.left = null. The chain looks right when you follow right, but leftover left arrows make it a tree with loops.
• Returning the old top instead of dummy.right. The top is in the middle of the line.
• Keeping tail as a parameter. Each call needs to see the latest end of the line, so it must be a field.

What interviewers ask next

• Make a doubly linked chain, also circular (LeetCode 426). Same walk, but also set node.left = tail, and at the end hook the last spot to the first.
• Flatten a plain binary tree into a chain in preorder (LeetCode 114). Different order: for each spot, splice its left side between it and its right side.
• Do it with O(1) room. Use Morris (temporary ropes), or the reverse trick: walk right side, me, left side and push each spot onto the front of the chain.
• Turn the chain back into a balanced BST. Count it, then build the left half first while a finger walks the chain. O(n).

Remember this

Grown-up words: the conga line is a singly linked list made of tree nodes, left, me, right is an inorder traversal, the finger is a tail (or prev) pointer, the dummy spot is a sentinel node, and doing it without new spots is an in-place conversion.