Flatten Binary Tree to Linked List | Leetcode 114

Welcome to our deep dive on Flatten Binary Tree to Linked List (Leetcode 114). This problem tests your ability to manipulate tree pointers in-place without allocating extra memory for new nodes. It heavily builds on your understanding of pre-order tree traversal.

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Note: You must flatten the tree in-place.

Example: root = [1, 2, 5, 3, 4, null, 6] Output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]

Approach 1: Recursive Post-Order (Right, Left, Root)

If you strictly do a pre-order traversal (Root, Left, Right) and overwrite the right pointer as you go, you will accidentally overwrite and lose access to the right subtree before you get a chance to visit it!

The brilliant workaround is to traverse the tree in Reverse Post-Order (Right, Left, Root).

By tracking the previously_visited node, we can go all the way down to the bottom-rightmost node of the tree. As our recursion bubbles back up:

1. We set the current node's right pointer to the previously_visited node.
2. We set the current node's left pointer to null.
3. We update previously_visited to be the current node!

# 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
class Solution:
    def __init__(self):
        self.prev = None
        
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
            
        # Traverse Right, Left, Root (Reverse Post-Order)
        self.flatten(root.right)
        self.flatten(root.left)
        
        # Wire the current node to point to the previously processed node
        root.right = self.prev
        root.left = None
        
        # Move the prev pointer up to the current node 
        self.prev = root

Complexity Analysis

Approach 2: Iterative Morris Traversal (O(1) Space)

The recursive approach is elegant, but it requires O(N) stack space. Can we achieve optimal O(1) constant space? Yes, using a manipulation of Morris Traversal.

The core requirement of a pre-order flattening is that a node's entire left subtree must be processed before moving to its right subtree. Furthermore, the rightmost node of that left subtree needs to connect directly to the original right child!

Algorithm at current node:

1. If node has a left child, find the rightmost node deep within that left subtree.
2. Wire the right pointer of that rightmost node to node.right (saving our right branch from being lost).
3. Now that the right branch is safe, overwrite node.right to be node.left.
4. Set node.left to null.
5. Move node to node.right and repeat!

graph TD
    A["Node(1)"] --> B["Left(2)"]
    A --> C["Right(5)"]
    B --> D["Left(3)"]
    B --> E["Right(4)"]
    C --> F["Right(6)"]
    
    E -.->|"1. Wire rightmost left-child to original right"| C
    A -.->|"2. Move left branch to right"| B
    
    style E fill:#FF9800,stroke:#fff,stroke-width:2px,color:#fff

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        curr = root
        
        while curr:
            if curr.left:
                # 1. Find the rightmost node of the left subtree
                runner = curr.left
                while runner.right:
                    runner = runner.right
                    
                # 2. Wire it to the current node's right child
                runner.right = curr.right
                
                # 3. Move the entire left subtree over to the right
                curr.right = curr.left
                curr.left = None
                
            # 4. Step down to the next right node (which was previously our left child!)
            curr = curr.right

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (114)