Convert Binary tree into Doubly Linked List

The problem, simply

You get a binary tree. Rearrange its arrows so the nodes form a doubly linked list: a chain where each box points to the next box and also back to the box before it.

• The order of the chain is the left to right reading order of the tree (inorder).
• Use the same nodes. A node's left arrow becomes "back" and its right arrow becomes "next".
• Give back the first box of the chain, the head.

A story to remember it

Picture it

Examples

Way 1: the simple way

Read the tree left to right and put every node in a list. Then walk the list and set the arrows from neighbor to neighbor.

1. Do an inorder walk and add each node to a list.
2. For each position i, set left to the node at i - 1 (or null) and right to the node at i + 1 (or null).
3. Return the first node.

import java.util.*;

class Solution {
    public TreeNode toDLL(TreeNode root) {
        if (root == null) return null;
        List<TreeNode> order = new ArrayList<>();
        inorder(root, order);
        for (int i = 0; i < order.size(); i++) {
            TreeNode cur = order.get(i);
            cur.left = (i > 0) ? order.get(i - 1) : null;                  // back
            cur.right = (i + 1 < order.size()) ? order.get(i + 1) : null;  // next
        }
        return order.get(0);
    }

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

How long it takes: one walk and one pass over the list, O(n). Extra room: the list holds every node, O(n).

Way 2: the clever way

Skip the list. Link the nodes during the walk. Keep a finger prev on the last node added to the chain.

1. Walk the tree in inorder.
2. When you reach a node: if prev is null, this node is the head. Otherwise link prev.right = node and node.left = prev.
3. Move prev to this node and continue with the right side.

It is safe to change the arrows while walking. When we reach a node, its left side is already finished, so we can reuse node.left. And prev.right either was empty or pointed into the part we are walking now, which the walk already holds on to.

class Solution {
    private TreeNode prev, head;

    public TreeNode toDLL(TreeNode root) {
        prev = null;
        head = null;
        link(root);
        return head;
    }

    private void link(TreeNode node) {
        if (node == null) return;
        link(node.left);                 // everything on the left joins first
        if (prev == null) head = node;   // the leftmost node starts the chain
        else {
            prev.right = node;           // next
            node.left = prev;            // back
        }
        prev = node;
        link(node.right);
    }
}

How long it takes: each node is visited once, O(n). Extra room: only the waiting helpers, as many as the tree is tall, O(h). That is O(log n) for a bushy tree and O(n) for a stick shaped one.

Watch out for

• Not resetting prev and head between calls when they are fields.
• Linking only one way. A doubly linked list needs both prev.right = node and node.left = prev.
• The ends. The head's left and the tail's right should be null. Here they already are: the leftmost node has no left child, and the rightmost node has no right child.

What interviewers ask next

• Make it circular? After the walk, link the tail (prev) and the head: prev.right = head and head.left = prev. That is LeetCode 426.
• True O(1) extra room? Use a Morris walk, which borrows empty right arrows to find the way back instead of a call stack. It visits each node a few times but uses no stack.
• Flatten into a list in preorder using only right arrows? That is LeetCode 114. Walk right side first and keep a prev, or move each left subtree in between.
• Merge two search trees? Turn both into sorted chains like this, merge the chains, then build a balanced tree from the merged chain.

Remember this

Grown-up words: the line of kids is a doubly linked list, left to right reading is inorder traversal, the finger is the prev pointer, and the walk that borrows arrows is Morris traversal.