Problem Description

You are given the root of a binary tree. Your task is to flatten the tree into a "linked list" structure while modifying the tree in-place.

The flattening should follow these rules:

• Use the same TreeNode class for the flattened structure
• The right child pointer should point to the next node in the flattened list
• The left child pointer should always be set to null
• The order of nodes in the flattened list should match a pre-order traversal of the original binary tree (root → left subtree → right subtree)

For example, if you have a binary tree:

      1
     / \
    2   5
   / \   \
  3   4   6

After flattening, it should become:

1 → 2 → 3 → 4 → 5 → 6

Where each arrow represents a right pointer, and all left pointers are null.

The solution works by iteratively processing each node. For any node with a left subtree, it finds the rightmost node of that left subtree (the predecessor of the right subtree in pre-order traversal). It then reconnects the nodes by:

1. Moving the current node's right subtree to become the right child of the predecessor
2. Moving the left subtree to become the right child of the current node
3. Setting the left child to null
4. Moving to the next node (now the right child)

This process continues until all nodes are processed, resulting in a flattened tree that maintains the pre-order traversal sequence.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• We arrive at DFS: Since we're dealing with a tree and need to traverse it in a specific order (pre-order), DFS is the appropriate approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem.

This aligns perfectly with the solution approach because:

1. We need to traverse the tree in pre-order (root → left → right), which is a DFS traversal pattern
2. We need to visit and process each node while maintaining relationships between parent and child nodes
3. The solution manipulates the tree structure by finding predecessor nodes (rightmost node in left subtree) and reorganizing connections, which requires exploring the depth of subtrees
4. The iterative solution provided is essentially a modified DFS that processes nodes in pre-order while flattening the tree in-place

The DFS pattern is evident in how the solution:

• Processes the current node (root)
• Explores the left subtree to find the rightmost node
• Connects subtrees in pre-order sequence
• Continues traversing through the modified right pointers

Intuition

Think about what pre-order traversal gives us: root → left subtree → right subtree. In the flattened list, we want exactly this order, but everything should be connected via right pointers only.

The key insight is recognizing what happens during pre-order traversal: after we finish visiting all nodes in the left subtree, the very next node we visit is the root's right child. This means the last node visited in the left subtree should connect directly to the first node of the right subtree.

Let's trace through this idea. For any node with both left and right children:

• The left child and its entire subtree should come immediately after the current node
• The right child and its subtree should come after the entire left subtree
• The rightmost node of the left subtree is the last node visited before moving to the right subtree

This observation leads to our strategy: for each node, if it has a left child, we need to:

1. Find the rightmost node of the left subtree (this is the predecessor of the right subtree in pre-order)
2. Connect this predecessor to the current node's right subtree
3. Move the entire left subtree to become the right child of the current node
4. Clear the left pointer

By doing this iteratively from the root downward, we're essentially "rotating" the tree rightward while maintaining the pre-order sequence. Each left subtree gets moved to the right, and the original right subtree gets appended to the end of the moved left subtree.

The beauty of this approach is that we don't need extra space to store the pre-order traversal - we're rearranging the pointers in-place as we traverse, effectively "flattening" the tree one node at a time while preserving the exact visitation order that pre-order traversal would give us.

Solution Approach

The solution implements the predecessor node finding approach to flatten the binary tree in-place. Let's walk through the implementation step by step:

Algorithm Overview: We use an iterative approach that processes each node with a left child by finding its predecessor and reorganizing the tree structure.

Implementation Details:

1. Main Loop Structure:

   while root:
       # Process current node
       root = root.right

   We iterate through the tree using a while loop, moving to the right child after processing each node.

2. Finding the Predecessor Node: When the current node has a left child, we need to find the rightmost node of the left subtree:

   if root.left:
       pre = root.left
       while pre.right:
           pre = pre.right

   This traversal finds the last node that would be visited in the left subtree during pre-order traversal.

3. Reconnecting the Tree: Once we find the predecessor, we perform three critical pointer manipulations:

   pre.right = root.right  # Connect predecessor to right subtree
   root.right = root.left  # Move left subtree to right
   root.left = None        # Clear left pointer

Step-by-Step Process:

• Start at the root node
• If the current node has a left child:
  • Find the rightmost node in the left subtree (predecessor)
  • Attach the current node's right subtree to the predecessor's right pointer
  • Move the entire left subtree to become the right child of the current node
  • Set the left child to null
• Move to the next node (now the right child)
• Repeat until all nodes are processed

Time Complexity: O(n) where n is the number of nodes. Although we have nested loops, each node is visited at most twice - once as the current node and potentially once while finding a predecessor.

Space Complexity: O(1) as we only use a constant amount of extra space (the pre pointer) and modify the tree in-place without recursion.

This approach elegantly maintains the pre-order traversal sequence while transforming the tree structure into a linked list using only the right pointers.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider this binary tree:

    1
   / \
  2   3
 /
4

Initial State:

• Current node: 1 (has left child 2)
• Find predecessor: Start at node 2, check if it has a right child. It doesn't, so node 2 is the predecessor.
• Reconnect:
  • Set 2.right = 3 (predecessor points to original right subtree)
  • Set 1.right = 2 (move left subtree to right)
  • Set 1.left = null (clear left pointer)

After first iteration:

1
 \
  2
 / \
4   3

Second Iteration:

• Current node: 2 (has left child 4)
• Find predecessor: Start at node 4, it has no right child, so node 4 is the predecessor.
• Reconnect:
  • Set 4.right = 3 (predecessor points to node 2's right subtree)
  • Set 2.right = 4 (move left subtree to right)
  • Set 2.left = null (clear left pointer)

After second iteration:

1
 \
  2
   \
    4
     \
      3

Third Iteration:

• Current node: 4 (no left child, skip processing)
• Move to 4.right = 3

Fourth Iteration:

• Current node: 3 (no left child, skip processing)
• Move to 3.right = null, exit loop

Final Result: The tree is now flattened: 1 → 2 → 4 → 3

Each node only has a right child, all left pointers are null, and the order matches the pre-order traversal of the original tree (root: 1, left subtree: 2→4, right subtree: 3).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm visits each node in the tree exactly once. For each node that has a left subtree, it finds the rightmost node of that left subtree. While this involves traversing down the right spine of the left subtree, each edge in the tree is traversed at most once throughout the entire algorithm. Since a tree with n nodes has n-1 edges, and each edge is visited at most once, the total time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It modifies the tree in-place using Morris Traversal technique, utilizing only two pointer variables (root and pre) regardless of the input size. No recursion stack or additional data structures are used, making the space complexity constant.

Common Pitfalls

1. Losing the Right Subtree Reference

The Pitfall: A common mistake is directly moving the left subtree to the right position without first preserving the original right subtree. If you write:

current.right = current.left  # Wrong! Original right subtree is lost
current.left = None

The original right subtree gets orphaned and disconnected from the tree entirely.

Why It Happens: When reassigning pointers, it's easy to forget that we need to maintain all nodes in the tree. The original right subtree must be reattached somewhere before we overwrite the pointer.

The Solution: Always attach the original right subtree to the predecessor node BEFORE moving the left subtree:

predecessor.right = current.right  # Save right subtree first
current.right = current.left       # Then move left to right
current.left = None                # Finally clear left

2. Incorrect Predecessor Finding

The Pitfall: Some implementations might try to find the predecessor by going to the rightmost node of the entire tree or using incorrect traversal:

# Wrong approach - this finds rightmost of entire tree
predecessor = root
while predecessor.right:
    predecessor = predecessor.right

Why It Happens: Confusion about what "predecessor" means in this context. We need the rightmost node of the LEFT subtree specifically, not the global rightmost node.

The Solution: Always start the predecessor search from the left child of the current node:

predecessor = current.left  # Start from left child
while predecessor.right:    # Then go all the way right
    predecessor = predecessor.right

3. Modifying Node References While Traversing

The Pitfall: Using a recursive approach or maintaining parent pointers can lead to issues when the tree structure changes during traversal:

# Problematic recursive approach
def flatten(self, root):
    if not root:
        return
  
    left = root.left   # These references become invalid
    right = root.right # after modifying the tree
  
    self.flatten(left)
    self.flatten(right)
  
    # Tree structure has changed, connections might be wrong

Why It Happens: Recursive solutions process subtrees independently, but the flattening operation changes the tree structure, making cached references potentially invalid.

The Solution: Use the iterative approach that processes nodes in a controlled manner, always moving forward through the modified structure:

while current:
    # Process and modify current node
    # Move to the next node in the modified structure
    current = current.right

This ensures we're always working with the current state of the tree.