The key insight here is that inorder traversal visits nodes in exactly the order we want them in the list. So the problem reduces to: run an inorder traversal, and as we visit each node, stitch it into the doubly linked list using the existing left and right pointers. No extra memory needed beyond the call stack.

Understanding the Structure

In a doubly linked list built from a tree, each node's left pointer becomes the "previous" pointer, and right becomes the "next" pointer. Since we're doing this in-place, we're literally just rewiring the existing child pointers.

Let's think about what we need to track during traversal:

The previously visited node, so we can link it forward to the current node.
The head of the list, which is just the first node we visit (the leftmost node in the tree).

At each step during inorder traversal, when we're at current and prev is the last node we processed, we set prev.right = current and current.left = prev. Then we advance prev = current.

Walkthrough with an Example

Consider this tree:

Inorder traversal visits: 1, 2, 3, 4, 5. The resulting doubly linked list should be:

1 <-> 2 <-> 3 <-> 4 <-> 5

The head is node 1 (leftmost). We build the links as we go. After visiting node 1, prev = 1. When we visit node 2, we set 1.right = 2 and 2.left = 1. And so on.

The Implementation

We use a helper that carries prev as a mutable reference. In Python, a clean way to do this is to use a list of one element (acting as a mutable cell), or we can use instance variables on a helper class. Here we'll use a simple wrapper approach:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def tree_to_doubly_list(root):
    if not root:
        return None

    head = None
    prev = None

    def inorder(node):
        nonlocal head, prev

        if not node:
            return

        # Visit left subtree
        inorder(node.left)

        # Process current node
        if prev:
            # Link prev forward to current
            prev.right = node
            node.left = prev
        else:
            # This is the first node visited: it becomes the head
            head = node

        prev = node

        # Visit right subtree
        inorder(node.right)

    inorder(root)

    # At this point, prev is the last node (rightmost)
    # The problem typically asks for a non-circular list,
    # but if circular is required, add: head.left = prev; prev.right = head

    return head

Let's trace through the example. When we visit node 1, prev is None, so we set head = node 1. When we visit node 2, prev = 1, so we link 1.right = 2 and 2.left = 1. Continuing: 2.right = 3, 3.left = 2, then 3.right = 4, 4.left = 3, then 4.right = 5, 5.left = 4. The head returned is node 1. Exactly right.

Complexity Analysis

Time: $O(n)$. We visit every node exactly once.
Space: $O(h)$ where $h$ is the height of the tree, due to the recursion stack. For a balanced tree this is $O(\log n)$, and $O(n)$ in the worst case (a skewed tree).

Iterative Variant

If we want to avoid recursion entirely (to sidestep stack overflow on very deep trees), we can replicate the inorder traversal iteratively using an explicit stack:

def tree_to_doubly_list_iterative(root):
    if not root:
        return None

    stack = []
    current = root
    head = None
    prev = None

    while stack or current:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()

        # Process current node
        if prev:
            prev.right = current
            current.left = prev
        else:
            head = current

        prev = current

        # Move to right subtree
        current = current.right

    return head

The logic is identical. We just manage the "where to go next" state explicitly with a stack rather than relying on the call stack.

Common Follow-ups

What if the list needs to be circular? After the traversal, prev holds the tail. We just add two lines: prev.right = head and head.left = prev. The rest of the logic is unchanged.

What if the tree has duplicate values? No issue. The algorithm is purely structural and doesn't compare values.

Can we do it without recursion or an explicit stack? Yes, using Morris traversal, which runs in $O(1)$ extra space by temporarily threading the tree. It's considerably more complex to implement correctly, but the idea is to use the rightmost node of a left subtree as a temporary "thread" back to the current node, letting us know when we've finished visiting a left subtree.

2099. Binary Tree to List

Similar Questions