Binary Tree to Doubly Linked List

Medium TUF ID 62 SDE

Problem

You are given the root of a binary tree. Convert it in place into a doubly linked list and return the head of that list. Reuse the tree’s own nodes, do not allocate new ones:

a node’s left pointer becomes its previous pointer,
a node’s right pointer becomes its next pointer,
the nodes must appear in the list in the same order as an inorder traversal of the tree (left subtree, node, right subtree).

The head is therefore the leftmost node of the tree, not the root. An empty tree gives an empty list (null).

Constraints: up to 10^5 nodes. Node values play no role: the order comes from the tree’s shape, so duplicates are fine and the tree need not be a BST.

The node type used throughout is a plain binary tree node with fields data, left and right.

Example 1

          10
         /  \
       12    15
      /  \   /
     25  30 36

list: 25 <-> 12 <-> 30 <-> 10 <-> 36 <-> 15

Inorder visits the left subtree of 10 (25, 12, 30), then 10, then its right subtree (36, 15).

Example 2

       1
      / \
     3   2

list: 3 <-> 1 <-> 2

The head is 3, whose previous pointer is null; the tail is 2, whose next pointer is null.

Approach 1: Brute force, collect the inorder sequence then relink

Intuition. The required list order is exactly inorder. If we first write down the nodes, as references, in inorder into an array, the problem becomes trivial: the node at position i points back to position i - 1 and forward to position i + 1. We store references rather than values, so the final list is still made of the original nodes. The cost is the array of n references.

Rewriting pointers is safe here because the traversal has completely finished before the first pointer is touched. Nothing needs the tree shape any more.

Algorithm.

Run a recursive inorder traversal and append every node to a list order.
For each index i, set left to order[i - 1] (or null for i = 0) and right to order[i + 1] (or null for the last index).
Return order[0], or null if the tree was empty.

static Node bruteForce(Node root) {
    List<Node> order = new ArrayList<>();
    collectInorder(root, order);
    for (int i = 0; i < order.size(); i++) {
        Node node = order.get(i);
        node.left = i > 0 ? order.get(i - 1) : null;
        node.right = i + 1 < order.size() ? order.get(i + 1) : null;
    }
    return order.isEmpty() ? null : order.get(0);
}

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

Complexity. Time O(n): each node is visited once by the traversal and once by the relinking loop. Space O(n) for the list, plus O(h) recursion stack where h is the tree height.

Approach 2: Better, link while traversing

Intuition. The array in approach 1 is only ever used to look at the previous element. An inorder traversal visits nodes in final list order, so at the moment we visit a node, the node that should precede it in the list is simply the last node we visited. Keep that one reference, prev, and link the pair on the spot: prev.right = node and node.left = prev. The very first visited node has prev == null and becomes the head.

The interesting question is why overwriting pointers in the middle of a traversal does not break it:

node.left is overwritten only after the recursive call on the left subtree has returned, so that pointer is never read again.
prev is the inorder predecessor of node. Either prev is the rightmost node of node’s left subtree, in which case prev.right was null anyway, or node is the leftmost node of prev’s right subtree. In that second case the recursive call for prev had already passed prev.right down as an argument before we overwrite it, so the traversal still reaches the whole right subtree.

Java cannot pass a local variable by reference, so the method carries head and prev in a two-cell array. Static fields would also work but make the method unsafe to call twice without resetting them, which is a classic source of wrong answers on online judges.

Algorithm.

Keep state[0] = head and state[1] = prev, both initially null.
link(node): if node is null, return. Recurse on node.left.
Set node.left = prev. If prev is null, node is the head; otherwise set prev.right = node.
Set prev = node and recurse on node.right.
Return head. The last node’s right is already null because it is the rightmost node of the tree.

static Node better(Node root) {
    Node[] state = new Node[2];                         // state[0] = head, state[1] = prev (last node linked)
    link(root, state);
    return state[0];
}

static void link(Node node, Node[] state) {
    if (node == null) return;
    link(node.left, state);                             // the whole left subtree is linked before node
    Node prev = state[1];
    node.left = prev;                                   // safe: node.left is no longer needed
    if (prev == null) state[0] = node; else prev.right = node;
    state[1] = node;
    link(node.right, state);                            // node.right was read before anyone overwrote it
}

Complexity. Time O(n), one visit per node. Space O(h) for the recursion only. That is O(log n) for a balanced tree but O(n) for a skewed one, and a 10^5-deep recursion can overflow Java’s default thread stack.

Approach 3: Optimal, rotate the tree into a vine

Intuition. A right rotation never changes the inorder order of a tree. That is the property that lets balanced BSTs rotate freely:

        rest                l
        /  \              /   \
       l    C    ==>     A    rest
      / \                     /  \
     A   B                   B    C

inorder before: A l B rest C      inorder after: A l B rest C

Each rotation lifts a left child up and pushes its parent to the right. If we keep rotating at any node that still has a left child, the tree eventually has no left children at all. It is then a “vine”: a chain that goes only to the right, and since rotations preserve inorder, the chain lists the nodes in exactly inorder. In other words, the right pointers already form the forward links of our list. One more walk along the chain fills in the left (previous) pointers.

This is the first phase of the Day-Stout-Warren tree balancing algorithm. It needs no array, no recursion and no stack, only a handful of pointers.

Algorithm.

Create a dummy node with dummy.right = root. tail (initially dummy) is the last node already in final position, and rest (initially root) is the subtree hanging below it that still has to be straightened.
While rest is not null:
- If rest.left is null, nothing in rest’s subtree is smaller than rest, so rest is the next list node. Move tail = rest and rest = rest.right.
- Otherwise right-rotate at rest: l = rest.left, rest.left = l.right, l.right = rest, then hang l under the vine with tail.right = l and continue from rest = l.
Walk from dummy.right along right pointers, setting each node’s left to the previous node.
Return dummy.right.

static Node optimal(Node root) {
    Node dummy = new Node(0);                           // dummy.right is always the head of the vine
    dummy.right = root;
    Node tail = dummy;                                  // last node already in its final position
    Node rest = root;                                   // subtree still to be straightened
    while (rest != null) {
        if (rest.left == null) {                        // nothing in this subtree is smaller: rest is next
            tail = rest;
            rest = rest.right;
        } else {                                        // right rotation: the left child moves up
            Node l = rest.left;
            rest.left = l.right;
            l.right = rest;
            rest = l;
            tail.right = l;
        }
    }
    Node prev = null;
    for (Node cur = dummy.right; cur != null; cur = cur.right) {
        cur.left = prev;                                // second pass: add the backward links
        prev = cur;
    }
    return dummy.right;
}

Why it is linear. Count the nodes on the right spine that starts at dummy. Every rotation adds one node (the lifted l) to that spine, and a node on the spine never leaves it, so there are at most n rotations. Every other loop step moves tail forward by one node, which also happens at most n times.

Dry run on Example 2 (root 1 with left child 3 and right child 2):

step	rest	rest.left	action	spine from dummy
1	1	3	rotate: `3` goes up, `1` becomes `3.right`	3, 1, 2
2	3	null	`tail = 3`, move right	3, 1, 2
3	1	null	`tail = 1`, move right	3, 1, 2
4	2	null	`tail = 2`, move right	3, 1, 2
5	null		stop; second pass sets `3.left = null`, `1.left = 3`, `2.left = 1`

Complexity. Time O(n) as argued above. Space O(1) extra: one dummy node and a few references, independent of the tree’s height. This makes it the only one of the three that is safe on a 10^5-node skewed tree without enlarging the stack.

Edge cases and pitfalls

Empty tree. All three methods return null: the collected list is empty, head is never set, and dummy.right stays null.
Returning the root. The head is the leftmost node. Returning root gives a list that silently skips the whole left subtree when walked forward.
Allocating new nodes. Building a fresh list of copies is a different (easier) problem. The tests in the Java file check node identity to make sure the list reuses the original nodes.
Stale static state. If head and prev live in static fields, a second call starts with the previous tree’s tail. Keep the state local, as approach 2 does.
Skewed trees and recursion depth. Approaches 1 and 2 recurse h levels deep. For a degenerate tree with 10^5 nodes this can throw StackOverflowError; approach 3 is iterative.
Duplicates and non-BST trees. Order comes from structure, not values, so neither matters. The tests include an all-equal tree and a zig-zag shaped tree.
Circular variant. LeetCode’s version (BST to sorted circular doubly linked list) needs one extra step after any of these methods: connect the head and the tail to each other.

Flatten Binary Tree to Linked List rewires a tree in place into a preorder, singly linked chain.
Inorder Traversal of Binary Tree is the traversal whose order the list must follow.
Morris Inorder Traversal of a Binary Tree is another O(1)-space trick that temporarily rewires right pointers.
Introduction to Doubly LL covers the previous and next pointer invariants used here.
Merge 2 BST’s is commonly solved by flattening both trees into sorted lists first.

Binary Tree to Doubly Linked List

Problem

Approach 1: Brute force, collect the inorder sequence then relink

Approach 2: Better, link while traversing

Approach 3: Optimal, rotate the tree into a vine

Edge cases and pitfalls

Related problems