Flatten Binary Tree to Linked List

🎯

Flatten Binary Tree to Linked List

mediumTREEAmazonMicrosoftGoogle

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.

💡 This problem requires transforming a tree structure into a linked list in-place, which can be tricky because beginners often struggle with modifying pointers while preserving traversal order and avoiding extra space.

📋

Problem Statement

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.

💡

Example

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

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

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

• Single node tree → output is the node itself with left=null
• Tree with only left children → output is a right-skewed linked list
• Tree with only right children → output remains the same
• Empty tree (null root) → output is null

⚠️

Common Mistakes

Not setting left pointers to null

The output linked list still has left children, violating problem requirements

✅ Explicitly set node.left = null after rewiring

Losing subtree references when rewiring

Parts of the tree get disconnected and lost, leading to incorrect output

✅ Save references to subtrees before rewiring pointers

Using extra space when problem requires in-place

Solution may be accepted but is suboptimal and may be penalized in interviews

✅ Use recursive or iterative in-place approaches without auxiliary lists

Incorrect traversal order causing wrong linked list sequence

Flattened list does not follow preorder traversal order

✅ Use preorder traversal or reverse preorder with global pointer carefully

Stack overflow on deep recursion

Program crashes on very deep or skewed trees

✅ Consider iterative approach or tail recursion optimization if allowed

🧠

Brute Force (Preorder Traversal + Rebuild)

💡 This approach exists to build intuition by separating traversal from reconstruction, helping beginners understand the problem before optimizing.

Intuition

First, perform a preorder traversal to collect nodes in a list, then rebuild the tree into a linked list using that list.

Algorithm

1. Traverse the tree in preorder and store nodes in a list.
2. Iterate over the list and set each node's left pointer to null.
3. Set each node's right pointer to the next node in the list.
4. Ensure the last node's right pointer is null.

💡 Separating traversal and reconstruction clarifies the problem but uses extra space, which is a tradeoff to understand.

</>

Code

from typing import Optional, List

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

def flatten(root: Optional[TreeNode]) -> None:
    nodes: List[TreeNode] = []

    def preorder(node: Optional[TreeNode]):
        if not node:
            return
        nodes.append(node)
        preorder(node.left)
        preorder(node.right)

    preorder(root)

    for i in range(len(nodes) - 1):
        nodes[i].left = None
        nodes[i].right = nodes[i + 1]
    if nodes:
        nodes[-1].left = None
        nodes[-1].right = None

# Driver code to test
if __name__ == '__main__':
    # Build tree: 1
    #            /   \
    #           2     5
    #          / \     \
    #         3   4     6
    root = TreeNode(1,
                    TreeNode(2, TreeNode(3), TreeNode(4)),
                    TreeNode(5, None, TreeNode(6)))
    flatten(root)
    # Print flattened list
    curr = root
    while curr:
        print(curr.val, end=' -> ' if curr.right else '')
        curr = curr.right
    print()

Line Notes

nodes: List[TreeNode] = []Initialize list to store nodes in preorder

def preorder(node: Optional[TreeNode]):Define helper function for preorder traversal

nodes.append(node)Add current node to list to preserve traversal order

for i in range(len(nodes) - 1):Iterate to rewire nodes into linked list form

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class FlattenBinaryTree {
    public void flatten(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        preorder(root, nodes);
        for (int i = 0; i < nodes.size() - 1; i++) {
            nodes.get(i).left = null;
            nodes.get(i).right = nodes.get(i + 1);
        }
        if (!nodes.isEmpty()) {
            TreeNode last = nodes.get(nodes.size() - 1);
            last.left = null;
            last.right = null;
        }
    }

    private void preorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        nodes.add(node);
        preorder(node.left, nodes);
        preorder(node.right, nodes);
    }

    // Driver code
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        new FlattenBinaryTree().flatten(root);

        TreeNode curr = root;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.right != null) System.out.print(" -> ");
            curr = curr.right;
        }
        System.out.println();
    }
}

Line Notes

List<TreeNode> nodes = new ArrayList<>();Create list to hold nodes in preorder

preorder(root, nodes);Collect nodes in preorder traversal

nodes.get(i).left = null;Set left pointer to null to flatten

nodes.get(i).right = nodes.get(i + 1);Link current node to next node in list

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> nodes;
        preorder(root, nodes);
        for (size_t i = 0; i + 1 < nodes.size(); ++i) {
            nodes[i]->left = nullptr;
            nodes[i]->right = nodes[i + 1];
        }
        if (!nodes.empty()) {
            nodes.back()->left = nullptr;
            nodes.back()->right = nullptr;
        }
    }

private:
    void preorder(TreeNode* node, vector<TreeNode*>& nodes) {
        if (!node) return;
        nodes.push_back(node);
        preorder(node->left, nodes);
        preorder(node->right, nodes);
    }
};

// Driver code
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    Solution sol;
    sol.flatten(root);

    TreeNode* curr = root;
    while (curr) {
        cout << curr->val;
        if (curr->right) cout << " -> ";
        curr = curr->right;
    }
    cout << endl;
    return 0;
}

Line Notes

vector<TreeNode*> nodes;Store nodes in preorder traversal order

void preorder(TreeNode* node, vector<TreeNode*>& nodes)Helper function to collect nodes recursively

nodes[i]->left = nullptr;Remove left child to flatten tree

nodes[i]->right = nodes[i + 1];Link current node to next node in preorder

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function flatten(root) {
    const nodes = [];
    function preorder(node) {
        if (!node) return;
        nodes.push(node);
        preorder(node.left);
        preorder(node.right);
    }
    preorder(root);
    for (let i = 0; i < nodes.length - 1; i++) {
        nodes[i].left = null;
        nodes[i].right = nodes[i + 1];
    }
    if (nodes.length > 0) {
        nodes[nodes.length - 1].left = null;
        nodes[nodes.length - 1].right = null;
    }
}

// Driver code
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(3), new TreeNode(4)),
    new TreeNode(5, null, new TreeNode(6))
);
flatten(root);
let curr = root;
const result = [];
while (curr) {
    result.push(curr.val);
    curr = curr.right;
}
console.log(result.join(' -> '));

Line Notes

const nodes = [];Array to hold nodes in preorder

function preorder(node)Recursive helper to traverse tree preorder

nodes.push(node);Add current node to traversal list

nodes[i].left = null;Set left pointer to null to flatten

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit each node once during preorder traversal and store all nodes in a list, then iterate once more to rewire pointers.

💡 For n=20 nodes, this means about 40 operations for traversal and rewiring, which is manageable but uses extra memory.

Interview Verdict: Accepted but uses extra space

This approach works but is not optimal because it uses extra space; it is useful to understand the problem before optimizing.

🧠

Better (Recursive In-place Flattening Using Postorder)

💡 This approach improves space by flattening the tree in-place using recursion, helping learners understand pointer manipulation without extra storage.

Intuition

Recursively flatten left and right subtrees, then rewire the current node's right pointer to the flattened left subtree, and append the flattened right subtree at the end.

Algorithm

1. Recursively flatten left subtree.
2. Recursively flatten right subtree.
3. If left subtree exists, find its rightmost node.
4. Attach the original right subtree to the rightmost node of the left subtree.
5. Set current node's right pointer to left subtree and left pointer to null.

💡 The challenge is correctly finding the rightmost node and rewiring pointers without losing any subtree.

</>

Code

from typing import Optional

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

def flatten(root: Optional[TreeNode]) -> None:
    if not root:
        return
    flatten(root.left)
    flatten(root.right)

    if root.left:
        rightmost = root.left
        while rightmost.right:
            rightmost = rightmost.right
        rightmost.right = root.right
        root.right = root.left
        root.left = None

# Driver code
if __name__ == '__main__':
    root = TreeNode(1,
                    TreeNode(2, TreeNode(3), TreeNode(4)),
                    TreeNode(5, None, TreeNode(6)))
    flatten(root)
    curr = root
    while curr:
        print(curr.val, end=' -> ' if curr.right else '')
        curr = curr.right
    print()

Line Notes

if not root:Base case to stop recursion at null nodes

flatten(root.left)Recursively flatten left subtree first

while rightmost.right:Find rightmost node of left subtree to attach right subtree

root.left = NoneSet left pointer to null after rewiring

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class FlattenBinaryTree {
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left);
        flatten(root.right);

        if (root.left != null) {
            TreeNode rightmost = root.left;
            while (rightmost.right != null) {
                rightmost = rightmost.right;
            }
            rightmost.right = root.right;
            root.right = root.left;
            root.left = null;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        new FlattenBinaryTree().flatten(root);

        TreeNode curr = root;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.right != null) System.out.print(" -> ");
            curr = curr.right;
        }
        System.out.println();
    }
}

Line Notes

if (root == null) return;Stop recursion at leaf nodes

flatten(root.left);Flatten left subtree recursively

while (rightmost.right != null)Locate rightmost node of left subtree

root.left = null;Remove left child after rewiring

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->left);
        flatten(root->right);

        if (root->left) {
            TreeNode* rightmost = root->left;
            while (rightmost->right) {
                rightmost = rightmost->right;
            }
            rightmost->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    Solution sol;
    sol.flatten(root);

    TreeNode* curr = root;
    while (curr) {
        cout << curr->val;
        if (curr->right) cout << " -> ";
        curr = curr->right;
    }
    cout << endl;
    return 0;
}

Line Notes

if (!root) return;Base case to end recursion

flatten(root->left);Recursively flatten left subtree

while (rightmost->right)Find rightmost node of left subtree

root->left = nullptr;Clear left pointer after rewiring

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function flatten(root) {
    if (!root) return;
    flatten(root.left);
    flatten(root.right);

    if (root.left) {
        let rightmost = root.left;
        while (rightmost.right) {
            rightmost = rightmost.right;
        }
        rightmost.right = root.right;
        root.right = root.left;
        root.left = null;
    }
}

// Driver code
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(3), new TreeNode(4)),
    new TreeNode(5, null, new TreeNode(6))
);
flatten(root);
let curr = root;
const result = [];
while (curr) {
    result.push(curr.val);
    curr = curr.right;
}
console.log(result.join(' -> '));

Line Notes

if (!root) return;Stop recursion at null nodes

flatten(root.left);Flatten left subtree recursively

while (rightmost.right)Traverse to rightmost node of left subtree

root.left = null;Remove left pointer after rearrangement

⏱

Complexity

TimeO(n^2) in worst case

SpaceO(h) due to recursion stack, where h is tree height

Each node is visited once, but finding the rightmost node can take O(n) in skewed trees, leading to O(n^2) worst case.

💡 For balanced trees, this is closer to O(n), but for skewed trees with 20 nodes, it could be up to 400 operations.

Interview Verdict: Accepted but can be slow on skewed trees

This approach is better space-wise but can be inefficient time-wise due to repeated traversal to find rightmost nodes.

🧠

Optimal (Reverse Preorder Traversal with a Global Pointer)

💡 This approach is optimal and elegant, using a reverse preorder traversal and a global pointer to flatten the tree in-place without extra traversal.

Intuition

Traverse the tree in reverse preorder (right, left, root), and at each node, set its right pointer to the previously visited node, effectively building the linked list backwards.

Algorithm

1. Initialize a global pointer 'prev' as null.
2. Traverse the tree recursively in right-left-root order.
3. At each node, set node.right = prev and node.left = null.
4. Update prev to the current node.

💡 This approach avoids searching for rightmost nodes by building the linked list from the bottom up.

</>

Code

from typing import Optional

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

prev = None

def flatten(root: Optional[TreeNode]) -> None:
    global prev
    if not root:
        return
    flatten(root.right)
    flatten(root.left)
    root.right = prev
    root.left = None
    prev = root

# Driver code
if __name__ == '__main__':
    root = TreeNode(1,
                    TreeNode(2, TreeNode(3), TreeNode(4)),
                    TreeNode(5, None, TreeNode(6)))
    flatten(root)
    curr = root
    while curr:
        print(curr.val, end=' -> ' if curr.right else '')
        curr = curr.right
    print()

Line Notes

prev = NoneGlobal pointer to track previously processed node

flatten(root.right)Traverse right subtree first for reverse preorder

root.right = prevLink current node's right to previously processed node

prev = rootUpdate prev to current node for next iteration

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class FlattenBinaryTree {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        FlattenBinaryTree sol = new FlattenBinaryTree();
        sol.flatten(root);

        TreeNode curr = root;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.right != null) System.out.print(" -> ");
            curr = curr.right;
        }
        System.out.println();
    }
}

Line Notes

private TreeNode prev = null;Instance variable to keep track of last processed node

flatten(root.right);Process right subtree first for reverse preorder

root.right = prev;Set current node's right pointer to previously processed node

prev = root;Update prev to current node

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    TreeNode* prev = nullptr;
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = nullptr;
        prev = root;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    Solution sol;
    sol.flatten(root);

    TreeNode* curr = root;
    while (curr) {
        cout << curr->val;
        if (curr->right) cout << " -> ";
        curr = curr->right;
    }
    cout << endl;
    return 0;
}

Line Notes

TreeNode* prev = nullptr;Pointer to track previously processed node

flatten(root->right);Traverse right subtree first for reverse preorder

root->right = prev;Link current node's right to previously processed node

prev = root;Update prev pointer to current node

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

let prev = null;
function flatten(root) {
    if (!root) return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}

// Driver code
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(3), new TreeNode(4)),
    new TreeNode(5, null, new TreeNode(6))
);
flatten(root);
let curr = root;
const result = [];
while (curr) {
    result.push(curr.val);
    curr = curr.right;
}
console.log(result.join(' -> '));

Line Notes

let prev = null;Global variable to hold last processed node

flatten(root.right);Process right subtree first for reverse preorder

root.right = prev;Set current node's right pointer to previously processed node

prev = root;Update prev to current node for next iteration

⏱

Complexity

TimeO(n)

SpaceO(h) due to recursion stack, where h is tree height

Each node is visited once, and no extra traversal is needed to find rightmost nodes, making it efficient.

💡 For n=20 nodes, this means about 20 operations plus recursion overhead, which is optimal.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its efficiency and in-place operation.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal reverse preorder approach is recommended for interviews due to its efficiency and in-place operation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	Yes	Mention only - never code
2. Recursive In-place	O(n^2) worst case	O(h)	Yes (deep recursion)	No	Good to discuss, but not optimal
3. Optimal Reverse Preorder	O(n)	O(h)	Yes (deep recursion)	No	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to present each during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach using preorder traversal and rebuilding.Step 3: Discuss the recursive in-place approach and its tradeoffs.Step 4: Present the optimal reverse preorder traversal solution.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 2min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, pointer manipulation, in-place transformations, and optimization skills.

Common Follow-ups

• Can you flatten the tree without using extra space? → Use in-place recursive approach.
• What if the tree is very skewed? → Discuss recursion stack and iterative solutions.
• Can you do this iteratively? → Use a stack to simulate preorder traversal.
• How to restore the original tree? → Keep track of original pointers before flattening.

💡 These follow-ups test your ability to adapt the solution to constraints and think beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Asked to transform a tree into a linked list or linear structure; 2) In-place modification required; 3) Preorder traversal order is important; 4) Pointer rewiring involved.

Signature Phrases

flatten the treelinked list using right pointerspreorder traversal order

NOT This Pattern When

Problems that require building new data structures instead of in-place modification, or those focused on BFS traversal.

Similar Problems

Binary Tree to Linked List Variants - similar pointer rewiringFlatten N-ary Tree to Linked List - generalization to more childrenConvert BST to Sorted Doubly Linked List - different traversal but similar pointer manipulation

Practice

1. You need to determine if a binary tree is height-balanced, meaning the heights of the two child subtrees of any node never differ by more than one. Which approach guarantees an optimal O(n) time solution without redundant height computations?

easy

A. Use a top-down recursive approach that checks balance only at the root node.

B. Compute height for each node separately and check balance at each node recursively.

C. Perform a breadth-first traversal and check balance by comparing subtree sizes at each level.

D. Use a postorder traversal that returns height and balance status simultaneously, stopping early if imbalance is found.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking balance at every node efficiently without recomputing heights multiple times.

2. Step 2: Identify the approach that avoids redundant work

   Postorder traversal that returns both height and balance status in one pass allows early exit on imbalance and avoids repeated height calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Postorder traversal with early exit is O(n) and avoids recomputation [OK]

Hint: Postorder traversal with early exit avoids repeated height calls [OK]

Common Mistakes:

• Checking balance only at root misses subtree imbalances
• Computing height separately for each node causes O(n²) time
• Using BFS to check balance is incorrect as balance depends on subtree heights

2. Given the following code snippet for checking if a binary tree is symmetric, what is the final return value when called with the tree root = TreeNode(1, TreeNode(2), TreeNode(2))?

from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return t1 == t2
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

root = TreeNode(1, TreeNode(2), TreeNode(2))
print(isSymmetric(root))  # What is the output?

easy

A. false

B. Raises an exception

C. null

D. true

Solution

1. Step 1: Trace isMirror on root.left and root.right nodes with value 2

   Both nodes exist and have equal values, so recursion continues.

2. Step 2: Recursively check left.left vs right.right and left.right vs right.left (both null)

   Since both pairs are null, isMirror returns true for these calls, so overall returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Symmetric tree with equal child nodes returns true [OK]

Hint: Symmetric tree with equal children returns true [OK]

Common Mistakes:

• Confusing null checks causing exceptions
• Returning false prematurely on equal nodes
• Misreading recursion base cases

3. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:

medium

A. O(n), but with O(n) auxiliary space for the queue at the widest level

B. O(n), because each node is visited exactly once in BFS

C. O(n log n), because each level requires sorting nodes

D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

1. Step 1: Identify time complexity

   BFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity and common misconception

   Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node enqueued and dequeued once; max queue size O(n) [OK]

Hint: BFS visits each node once; space depends on max level width [OK]

Common Mistakes:

• Assuming multiple visits per node
• Confusing sorting with traversal
• Ignoring queue space usage

4. The following code attempts to count the number of paths summing to targetSum using iterative DFS and prefix sums. Which line contains a subtle bug that causes incorrect path counts?

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                # BUG: Missing decrement of prefix_counts on backtrack
                # prefix_counts[current_sum] -= 1
                pass

        return result

medium

A. Line where prefix_counts[current_sum] should be decremented but is missing

B. Line where prefix_counts[current_sum] is incremented

C. Line where current_sum is incremented by node.val

D. Line where stack appends left and right children

Solution

1. Step 1: Identify prefix_counts usage

   prefix_counts tracks how many times a prefix sum has occurred along the current path.

2. Step 2: Recognize missing decrement on backtrack

   Failing to decrement prefix_counts[current_sum] when backtracking causes counts to accumulate incorrectly across branches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement leads to overcounting paths [OK]

Hint: Always decrement prefix_counts on backtrack [OK]

Common Mistakes:

• Not decrementing prefix_counts after visiting children
• Assuming prefix_counts only grows
• Confusing when to mark node as visited

5. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?

hard

A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.

B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.

C. Switch to preorder and inorder traversals which do not have duplicates.

D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

1. Step 1: Understand the impact of duplicates

   Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.

2. Step 2: Required modification

   Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.

3. Step 3: Why other options fail

   Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value is necessary for duplicates [OK]

Hint: Duplicates require tracking all indices, not just one [OK]

Common Mistakes:

• Ignoring duplicates in hash map
• Assuming unique values always
• Switching traversal types incorrectly