LeetCode 114 - Flatten Binary Tree to Linked List

Difficulty: 🟡 Medium
Topics: Linked List, Stack, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to transform a binary tree into a flattened structure that behaves like a singly linked list. The transformation must happen in-place, meaning we are not supposed to create an entirely new tree or list structure. Instead, we must rearrange the existing pointers inside the tree nodes.

The flattened structure must follow the order of a pre-order traversal. In a pre-order traversal, we always visit nodes in this order:

Current node
Left subtree
Right subtree

After flattening, every node's left pointer must become null, and the right pointer should point to the next node in the pre-order sequence.

For example, consider this tree:

Its pre-order traversal is:

1 -> 2 -> 3 -> 4 -> 5 -> 6

So the final flattened structure becomes:

The input is the root node of a binary tree. The output is not returned explicitly. Instead, we modify the original tree directly.

The constraints tell us that the tree contains at most 2000 nodes. This is small enough that even recursive solutions are acceptable in practice, although the follow-up specifically asks whether we can achieve O(1) extra space.

Several edge cases are important:

The tree may be empty (root = null)
The tree may contain only one node
The tree may already be flattened
The tree may be completely left-skewed
The tree may be completely right-skewed

A naive implementation can easily lose references to subtrees while rearranging pointers, so careful ordering of operations is essential.

Approaches

Brute Force Approach

A straightforward solution is to first perform a pre-order traversal and store all visited nodes in a list. Once we have the nodes in the correct order, we iterate through the list and reconnect the pointers.

The process works like this:

Traverse the tree in pre-order
Store each node in an array
Iterate through the array
Set each node's left pointer to null
Set each node's right pointer to the next node in the array

This solution is easy to understand because it separates traversal from reconstruction. Since pre-order traversal already gives the desired order, reconnecting the nodes produces the correct flattened structure.

However, this approach uses additional memory proportional to the number of nodes because all nodes are stored in an auxiliary list. The follow-up specifically asks for an in-place solution with constant extra space, so we need a better approach.

Optimal Approach

The key insight is that we can rearrange the tree during traversal without storing all nodes.

For each node:

If the node has a left subtree:

Find the rightmost node of the left subtree
Connect that node to the original right subtree
Move the left subtree to the right
Set the left pointer to null

This works because pre-order traversal always processes the left subtree before the right subtree. By inserting the left subtree between the current node and the original right subtree, we preserve the correct traversal order.

This technique is similar to Morris Traversal because it rewires pointers temporarily and avoids using recursion or an explicit stack.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Store pre-order traversal in an array, then reconnect nodes
Optimal	O(n)	O(1)	Rearrange pointers directly during traversal

Algorithm Walkthrough

Optimal In-Place Algorithm

Start with a pointer called current initialized to the root node.
Traverse the tree while current is not null.
For each node, check whether it has a left child.

If there is no left child, the node is already correctly positioned for the flattened structure, so move directly to current.right. 4. If a left child exists, we need to insert the left subtree between the current node and its original right subtree. 5. Find the rightmost node in the current node's left subtree.

This node represents the final node visited in the left subtree during pre-order traversal. 6. Connect the rightmost node's right pointer to the current node's original right subtree.

This preserves the nodes that would otherwise be disconnected. 7. Move the left subtree to the right side:

current.right = current.left

Set the left pointer to null because the flattened structure must not contain left children.
Move current to current.right and continue the process.
Repeat until all nodes have been processed.

Why it works

The algorithm maintains the invariant that every processed node already satisfies the flattened linked-list structure.

For each node, the left subtree must appear immediately after the node in pre-order traversal. By moving the left subtree to the right and attaching the original right subtree to the end of the moved subtree, we preserve the exact pre-order ordering.

Since every node is rewired exactly once and we never lose references to any subtree, the final structure is a valid flattened tree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        current = root
        
        while current:
            
            if current.left:
                
                # Find the rightmost node of the left subtree
                predecessor = current.left
                
                while predecessor.right:
                    predecessor = predecessor.right
                
                # Connect original right subtree
                predecessor.right = current.right
                
                # Move left subtree to the right
                current.right = current.left
                current.left = None
            
            # Move to next node
            current = current.right

The implementation uses a single pointer called current to traverse the tree iteratively.

Whenever a node has a left subtree, we locate the rightmost node inside that subtree. This node is important because it becomes the bridge between the moved left subtree and the original right subtree.

After rewiring the pointers, the left subtree becomes the right subtree, and the left pointer is cleared.

The algorithm proceeds iteratively until every node has been transformed into the flattened structure.

Because the tree is modified directly and no auxiliary data structures are used, the solution achieves constant extra space.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
    
    current := root
    
    for current != nil {
        
        if current.Left != nil {
            
            // Find rightmost node of left subtree
            predecessor := current.Left
            
            for predecessor.Right != nil {
                predecessor = predecessor.Right
            }
            
            // Connect original right subtree
            predecessor.Right = current.Right
            
            // Move left subtree to right
            current.Right = current.Left
            current.Left = nil
        }
        
        current = current.Right
    }
}

The Go implementation follows the same logic as the Python version.

Instead of None, Go uses nil for empty pointers. Pointer manipulation is explicit because Go structs are handled through references.

The algorithm still performs all modifications in-place and avoids recursion or additional collections.

Worked Examples

Example 1

Input:

Step-by-Step Trace

Current Node	Left Subtree Exists	Rightmost Node in Left Subtree	Tree Modification
1	Yes	4	Connect 4 → 5, move 2 subtree right
2	Yes	3	Connect 3 → 4, move 3 subtree right
3	No	N/A	Move forward
4	No	N/A	Move forward
5	No	N/A	Move forward
6	No	N/A	Move forward

After processing node 1:

After processing node 2:

Final flattened tree:

1 -> 2 -> 3 -> 4 -> 5 -> 6

Example 2

Input:

[]

The root is null, so the loop never executes.

Output:

[]

Example 3

Input:

There is only one node.

Since there is no left subtree, no rewiring occurs.

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited a constant number of times
Space	O(1)	Only a few pointer variables are used

Although the algorithm contains nested loops, the total work is still linear. Each edge in the tree is traversed only a limited number of times while searching for rightmost predecessors.

No recursion stack or auxiliary collection is used, so the extra space remains constant.

Test Cases

# Helper utilities

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

def flattened_values(root):
    values = []
    
    while root:
        values.append(root.val)
        
        # Ensure left pointers are removed
        assert root.left is None
        
        root = root.right
    
    return values

# Solution under test
class Solution:
    def flatten(self, root):
        current = root
        
        while current:
            if current.left:
                predecessor = current.left
                
                while predecessor.right:
                    predecessor = predecessor.right
                
                predecessor.right = current.right
                current.right = current.left
                current.left = None
            
            current = current.right

# Test 1: Example case
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3),
        TreeNode(4)
    ),
    TreeNode(
        5,
        None,
        TreeNode(6)
    )
)

Solution().flatten(root)
assert flattened_values(root) == [1, 2, 3, 4, 5, 6]  # standard example

# Test 2: Empty tree
root = None
Solution().flatten(root)
assert root is None  # empty input

# Test 3: Single node
root = TreeNode(0)
Solution().flatten(root)
assert flattened_values(root) == [0]  # single-node tree

# Test 4: Already flattened
root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
Solution().flatten(root)
assert flattened_values(root) == [1, 2, 3]  # already right-skewed

# Test 5: Left-skewed tree
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)

Solution().flatten(root)
assert flattened_values(root) == [1, 2, 3, 4]  # only left children

# Test 6: Complete binary tree
root = TreeNode(
    1,
    TreeNode(2, TreeNode(3), TreeNode(4)),
    TreeNode(5, TreeNode(6), TreeNode(7))
)

Solution().flatten(root)
assert flattened_values(root) == [1, 2, 3, 4, 5, 6, 7]  # balanced tree

# Test 7: Mixed structure
root = TreeNode(
    1,
    TreeNode(2, None, TreeNode(3)),
    TreeNode(4)
)

Solution().flatten(root)
assert flattened_values(root) == [1, 2, 3, 4]  # mixed left/right structure

Test	Why
Standard example tree	Validates normal functionality
Empty tree	Ensures null input is handled safely
Single node	Verifies trivial case
Already flattened tree	Ensures algorithm does not corrupt valid structure
Left-skewed tree	Tests repeated left subtree rewiring
Complete binary tree	Verifies correctness on balanced trees
Mixed structure	Tests irregular subtree arrangements

Edge Cases

Empty Tree

An empty tree is represented by root = null. This case can easily cause null pointer errors if the implementation assumes the root always exists.

The algorithm handles this naturally because the traversal loop only executes while current is not null. If the tree is empty, the function exits immediately without performing any operations.

Single Node Tree

A tree containing only one node has no left or right children. Some implementations accidentally modify pointers unnecessarily or fail due to incorrect assumptions about subtree existence.

In this implementation, the node simply passes through the traversal loop once. Since there is no left subtree, no rewiring occurs, and the tree remains valid.

Completely Left-Skewed Tree

A left-skewed tree is one where every node only has a left child:

1
/
2
/
3
/
4

This case is important because every node requires rewiring. A buggy implementation might lose references to deeper nodes while rearranging pointers.

The algorithm safely handles this by always finding the rightmost node of the left subtree before changing any pointers. This guarantees that the remaining subtree remains connected throughout the transformation.

Already Flattened Tree

If the tree is already right-skewed and every left pointer is null, the algorithm should leave the structure unchanged.

Because the implementation only performs rewiring when current.left exists, already flattened trees are processed without modification.