#114

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Flatten Binary Tree to Linked List

Flatten a binary tree into a right-skewed linked list by manipulating pointers following a pre-order traversal, handling null nodes carefully.

linked list stack tree depth first search binary tree

Problem Statement

Given the root of a binary tree, flatten the tree into a 'linked list' following the pre-order traversal sequence. Each node's left child must be null, and the right child points to the next node in this traversal. The flattened structure should maintain the relative order of nodes exactly as encountered during pre-order processing, ensuring all original subtree nodes are linked properly without creating cycles or skipping nodes.

You must implement this transformation in-place without creating new tree nodes. The tree may be empty or contain up to 2000 nodes, each with values ranging from -100 to 100. Pay attention to edge cases such as single-node trees, fully left-skewed or right-skewed trees, and null nodes. Correct handling of left subtree reassignment and right-pointer propagation is essential to preserve the pre-order sequence. Examples include root = [1,2,5,3,4,null,6] flattening to [1,null,2,null,3,null,4,null,5,null,6].

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: root = []

Output: []

Example details omitted.

Example 3

Input: root = [0]

Output: [0]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Solution Approach

Recursive Pre-order Re-linking

Use a recursive approach where you traverse the tree in pre-order and flatten each subtree before connecting it. At each node, recursively flatten the left and right subtrees, then reassign the left subtree as the node's right child, and append the original right subtree at the end of the new right chain. This approach requires careful handling of null pointers to avoid breaking the linked-list sequence. Recursive backtracking ensures each node is processed only once while maintaining the pre-order pattern.

Iterative Stack-Based Flattening

Implement an iterative solution using a stack to simulate pre-order traversal. Push nodes onto the stack starting with the root, then process nodes by popping from the stack, setting the current node's right child to the next node from pre-order, and nullifying the left child. Push the right child first, then the left child to ensure correct order. This prevents losing subtrees and avoids recursion depth limits, but careful pointer management is required to maintain the flattened sequence without accidentally skipping nodes.

Morris Traversal Modification

Use a Morris traversal-like method to flatten the tree in-place without extra space. For each node with a left child, find the rightmost node of the left subtree and link its right pointer to the current node's right child. Then move the left subtree to the right and set the left pointer to null. Continue iterating to the right child. This method reduces space complexity compared to recursion or stack approaches but requires precise pointer reassignment to preserve the pre-order sequence and avoid overwriting important links.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once during pre-order traversal. Space complexity can be O(h) for recursion stack or O(n) for an explicit stack, or O(1) using the Morris traversal method. The provided complexities depend on the approach chosen, but all ensure linear processing relative to the number of nodes in the tree.

What Interviewers Usually Probe

Do you see how flattening in pre-order affects the linked list pointer reassignment?
Can you implement this in-place without using extra nodes or arrays?
Will you correctly handle edge cases such as null or single-node trees while preserving order?

Common Pitfalls or Variants

Common pitfalls

Forgetting to nullify the left child after moving the left subtree to the right can break the flattened structure.
Incorrectly appending the original right subtree may lead to nodes being skipped or duplicated.
Using a stack incorrectly may reverse the order of nodes, violating pre-order traversal sequence.

Follow-up variants

Flatten to a doubly-linked list preserving pre-order sequence with both next and previous pointers.
Flatten the tree in post-order instead of pre-order, testing pointer reassignment logic differently.
Flatten a n-ary tree to a linked list while maintaining pre-order traversal for multiple children per node.

FAQ

What is the main pattern used in Flatten Binary Tree to Linked List?

The primary pattern is linked-list pointer manipulation along a pre-order traversal, converting left subtrees to the right pointers while nullifying left children.

Can I solve this problem iteratively?

Yes, an iterative solution uses a stack to simulate pre-order traversal, pushing right then left children to maintain the correct sequence while reassigning pointers.

How do I handle null nodes in this flattening problem?

Null nodes should be skipped during traversal; ensure left children are nullified and right pointers link only valid nodes to maintain the linked list structure.

Is there a space-optimized approach?

Yes, using a Morris traversal-like technique allows in-place flattening with O(1) extra space by rewiring pointers without recursion or stack usage.

What are common mistakes when flattening the tree?

Common errors include not nullifying left children, misplacing the original right subtree, and reversing nodes due to incorrect stack push order, all of which break pre-order flattening.

terminal

Solution

Solution 1: Find Predecessor Node

The visit order of preorder traversal is "root, left subtree, right subtree". After the last node of the left subtree is visited, the right subtree node of the root node will be visited next.

# 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 flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        while root:
            if root.left:
                pre = root.left
                while pre.right:
                    pre = pre.right
                pre.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

Solution 2

#### Go

# 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 flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        while root:
            if root.left:
                pre = root.left
                while pre.right:
                    pre = pre.right
                pre.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

Continue Practicing

#116 populating next right pointers in each node #117 populating next right pointers in each node ii #94 binary tree inorder traversal