Flatten Binary Tree to Linked List

📋

Problem

Imagine you have a complex organizational chart represented as a binary tree, and you want to convert it into a simple linear chain of command without losing the order of hierarchy.

Given the root of a binary tree, flatten the tree into a 'linked list': specifically, the flattened tree should use the right child pointers to point to the next node in a preorder traversal, and all left child pointers should be set to null.

The number of nodes in the tree is in the range [1, 10^5].Node values are unique integers.You must flatten the tree in-place without using extra space for another data structure.

Edge cases: Single node tree → output is the node itself with left=nullTree with only left children → output is a right-skewed linked listTree with only right children → output remains the same

</>

IDE

def flatten(root: Optional[TreeNode]) -> None:public void flatten(TreeNode root)void flatten(TreeNode* root)function flatten(root)

def flatten(root: Optional[TreeNode]) -> None:
    # Write your solution here
    pass

class Solution {
    public void flatten(TreeNode root) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void flatten(TreeNode* root) {
    // Write your solution here
}

function flatten(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, null, 5, null, 6]Greedy approach attaching right subtree before flattening left subtree, losing nodes 2,3,4.✅ Flatten left subtree fully before attaching right subtree; use recursion or stack to preserve preorder.

Wrong: [1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 6]Repeated flattening causing duplication of nodes due to unbounded recursion confusion.✅ Flatten each node exactly once; avoid reusing nodes or duplicating pointers.

Wrong: [1, 2, 3, 4]Not setting left pointers to null, causing incorrect tree structure.✅ Explicitly set node.left = null after rearranging pointers.

Wrong: Runtime error or infinite recursionMissing base case for null root or leaf nodes.✅ Add base case: if root is null, return immediately.

Wrong: Timeout on large inputInefficient O(n^2) approach due to repeated subtree traversals.✅ Use O(n) approach with reverse preorder traversal and a global pointer.

✓

Test Cases

Handle null and single node trees carefully to avoid crashes.

Watch out for common algorithmic traps like greedy attachment or repeated flattening.

Focus on optimizing time complexity to handle large inputs efficiently.

t1_01basic

Input{"root":[1,2,5,3,4,null,6]}

Expected[1,null,2,null,3,null,4,null,5,null,6]

⏱ Performance - must finish in 2000ms

The tree is flattened to a linked list following preorder traversal: 1 -> 2 -> 3 -> 4 -> 5 -> 6, with all left pointers set to null.

💡 Think about preorder traversal and how to rearrange pointers in-place.

💡 Use the rightmost node of the left subtree to connect to the right subtree.

💡 For each node, attach the flattened left subtree to the right, then set left to null.

Why it failed: Incorrect output means pointers were not rearranged correctly in preorder. Fix by ensuring left subtree is flattened and attached to right, then left set to null.

✓ Correct preorder flattening with all left pointers null and right pointers forming the linked list.

t1_02basic

Input{"root":[1,null,2,null,3]}

Expected[1,null,2,null,3]

⏱ Performance - must finish in 2000ms

Tree with only right children remains unchanged after flattening.

💡 Check if the tree is already right-skewed; flattening should not alter structure.

💡 Ensure your code handles null left children gracefully.

💡 If left is null, just proceed to flatten right subtree.

Why it failed: Failing this test means your code incorrectly modifies right-skewed trees. Fix by skipping flattening when left child is null.

✓ Correctly handles trees with only right children without unnecessary changes.

t2_01edge

Input{"root":null}

Expectednull

⏱ Performance - must finish in 2000ms

Empty tree input should return null (no nodes to flatten).

💡 Check if root is null at the start.

💡 Return immediately if tree is empty.

💡 No changes needed if root is null.

Why it failed: Code crashes or returns non-null for null input. Fix by adding base case: if root is null, return immediately.

✓ Correctly handles empty tree input without errors.

t2_02edge

Input{"root":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node tree remains the same with left set to null.

💡 Single node means no children to flatten.

💡 Ensure left pointer is set to null even if already null.

💡 Return after processing single node.

Why it failed: Fails if left pointer is not set to null or node is altered incorrectly. Fix by explicitly setting root.left = null.

✓ Correctly handles single node tree with left pointer null.

t2_03edge

Input{"root":[1,2,null,3,null,4,null]}

Expected[1,null,2,null,3,null,4]

⏱ Performance - must finish in 2000ms

Tree with only left children is flattened into a right-skewed linked list.

💡 Left children must be moved to right pointers in preorder.

💡 Find rightmost node of left subtree to attach original right subtree.

💡 Set left pointers to null after rearrangement.

Why it failed: Fails if left children remain or order is incorrect. Fix by attaching left subtree to right and nullifying left pointers.

✓ Correctly transforms left-only tree into right-skewed linked list.

t3_01corner

Input{"root":[1,2,3,4,5,6,7]}

Expected[1,null,2,null,4,null,5,null,3,null,6,null,7]

⏱ Performance - must finish in 2000ms

Balanced tree flattened in preorder: left subtree fully flattened before right subtree.

💡 Preorder means root, then left subtree, then right subtree.

💡 Avoid greedy approach that attaches right subtree before flattening left.

💡 Use recursion or stack to ensure left subtree is fully flattened first.

Why it failed: Fails if right subtree is attached before left subtree is flattened (greedy trap). Fix by flattening left subtree fully before attaching right subtree.

✓ Correct preorder flattening respecting left subtree before right.

t3_02corner

Input{"root":[1,2,null,3,null,4,null,5]}

Expected[1,null,2,null,3,null,4,null,5]

⏱ Performance - must finish in 2000ms

Deep left-skewed tree flattened into right-skewed linked list preserving preorder.

💡 Watch for stack overflow or incorrect recursion on deep trees.

💡 Ensure you do not confuse 0/1 flattening with unbounded repetition.

💡 Flatten each subtree exactly once in preorder.

Why it failed: Fails if recursion incorrectly repeats nodes or misses nodes (0/1 vs unbounded confusion). Fix by flattening each node exactly once in preorder.

✓ Correctly flattens deep left-skewed tree without duplication.

t3_03corner

Input{"root":[1,null,2,null,3,null,4]}

Expected[1,null,2,null,3,null,4]

⏱ Performance - must finish in 2000ms

Right-skewed tree remains unchanged after flattening.

💡 Check that your code does not unnecessarily rearrange already flattened trees.

💡 Avoid off-by-one errors that might lose the last node.

💡 Ensure last node's left and right pointers are null.

Why it failed: Fails if last node's pointers are not set correctly or structure is altered. Fix by setting last node's left and right to null explicitly.

✓ Correctly handles right-skewed tree without changes.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large tree with 100 nodes to test O(n) time complexity; must complete within 2 seconds.

💡 Aim for O(n) time complexity using a single pass.

💡 Avoid repeated traversals or nested recursion that cause O(n^2) time.

💡 Use reverse preorder traversal with a global pointer to flatten efficiently.

Why it failed: TLE indicates inefficient approach, likely O(n^2) due to repeated subtree traversals. Fix by using a single pass reverse preorder traversal.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of max_sum after the function completes? Tree structure: ``` 1 / 2 3 ```

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

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = null
    gain_map = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gain_map.get(peek.left, 0), 0)
                right_gain = max(gain_map.get(peek.right, 0), 0)
                current_path_sum = peek.val + left_gain + right_gain
                max_sum = max(max_sum, current_path_sum)
                gain_map[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
    return max_sum

easy

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Trace left subtree gain

   Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.

2. Step 2: Trace root and right subtree

   Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of path 2 -> 1 -> 3 is 6 [OK]

Hint: Sum path 2->1->3 yields max sum 6 [OK]

Common Mistakes:

• Ignoring one child's gain leads to 5 or 4
• Off-by-one in gain_map updates
• Returning partial sums instead of max path sum

2. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

easy

A. True

B. False

C. Raises an exception due to null pointer

D. Returns True only if the root value equals targetSum

Solution

1. Step 1: Trace the path sums

   Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.

2. Step 2: Confirm code logic

   The DFS returns True as soon as it finds the matching path sum at a leaf node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Path 5↔4↔11↔2 sums to 22, so return True [OK]

Hint: Check all root-to-leaf paths, not just partial sums [OK]

Common Mistakes:

• Stopping at non-leaf nodes
• Ignoring leaf node condition

3. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n h) where h is tree height

Solution

1. Step 1: Analyze height computation calls

   Height is computed recursively for each node, and each height call traverses subtree nodes.

2. Step 2: Calculate total calls

   For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Repeated height calls cause quadratic time [OK]

Hint: Repeated height calls cause O(n²) time [OK]

Common Mistakes:

• Assuming height calls are O(1) leading to O(n) time
• Confusing height with depth or tree height h
• Thinking O(n log n) due to balanced tree assumption

4. The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.

def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx < mid:  # Bug here
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not null

medium

A. Line with 'if idx < mid:'

B. Line with 'return root is not null'

C. Line with 'root = root.right'

D. Line with 'left, right = 0, 2**(h - 1) - 1'

Solution

1. Step 1: Understand binary search condition

   The condition should be 'if idx <= mid' to correctly include mid index in left subtree.

2. Step 2: Identify impact of bug

   Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct binary search must include mid index [OK]

Hint: Binary search must use <= to include mid index [OK]

Common Mistakes:

• Using < instead of <= in binary search condition

5. Suppose the binary tree nodes can have an arbitrary number of children (not just two). Which modification to the BFS-based maximum depth algorithm correctly computes the maximum depth in this scenario?

hard

A. Replace 'if node.left' and 'if node.right' checks with iterating over 'node.children' list and enqueue each child.

B. Keep the same code but only enqueue 'node.left' and 'node.right' if they exist, ignoring other children.

C. Use DFS recursion only, as BFS cannot handle nodes with more than two children.

D. Modify the code to sum depths of all children instead of taking the maximum.

Solution

1. Step 1: Understand the problem extension

   Nodes now have arbitrary children, so left/right pointers are insufficient.

2. Step 2: Modify BFS to handle multiple children

   Iterate over 'node.children' list and enqueue each child to explore all branches correctly.

3. Step 3: Evaluate other options

   Ignoring children misses nodes; DFS can work but BFS is still valid; summing depths is incorrect for max depth.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Enqueue all children ensures full traversal for max depth [OK]

Hint: Enqueue all children nodes to handle arbitrary branching [OK]

Common Mistakes:

• Ignoring extra children
• Assuming binary tree structure
• Summing depths instead of max