Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogle

Flatten Binary Tree to Linked List

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize global pointer 'prev' as null

We start by setting the global pointer 'prev' to null before any recursion begins. This pointer will track the previously processed node in the flattened list.

💡 This initialization is crucial because 'prev' holds the last processed node, allowing us to link the current node's right pointer correctly.
Line:prev = None
💡 Understanding that 'prev' starts as null sets the base case for linking nodes from the bottom up.
📊
Flatten Binary Tree to Linked List - Watch the Algorithm Execute, Step by Step
Watching this step-by-step visualization reveals how the reverse preorder traversal and pointer rewiring work together to flatten the tree efficiently, which is difficult to grasp from code alone.
Step 1/14
·Active fill★Answer cell
123456
Current node: 1
123456
DFS Stack
1 (entered)
Current node: 5
123456
DFS Stack
5 (entered)1 (right_done)
Current node: 6
123456
DFS Stack
6 (entered)5 (right_done)1 (right_done)
Current node: 6
123456
DFS Stack
5 (right_done)1 (right_done)
123456
DFS Stack
5 (left_done)1 (right_done)
Current node: 5
123456
DFS Stack
1 (right_done)
Current node: 2
123456
DFS Stack
2 (entered)1 (left_done)
Current node: 4
123456
DFS Stack
2 (right_done)1 (left_done)
Current node: 4
123456
DFS Stack
2 (right_done)1 (left_done)
Current node: 3
123456
DFS Stack
3 (entered)2 (left_done)1 (left_done)
Current node: 3
123456
DFS Stack
1 (left_done)
Current node: 1
123456
123456
Result: [1, 2, 3, 4, 5, 6]

Key Takeaways

✓ The reverse preorder traversal (right-left-root) is essential to flatten the tree from the bottom up.

This traversal order is counterintuitive but necessary to link nodes correctly without losing references.

✓ The global 'prev' pointer tracks the last processed node, enabling each node to link to the next node in the flattened list.

Understanding 'prev' is key to grasping how the linked list is constructed incrementally.

✓ Setting each node's left pointer to null and right pointer to 'prev' rewires the tree into a singly linked list in-place.

This pointer manipulation is the core transformation that converts the tree structure.

Practice

(1/5)
1. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?
easy
A. 4
B. 2
C. 1
D. 3

Solution

  1. Step 1: Initialize variables

    inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
  2. Step 2: First iteration (i=3, node_val=20)

    top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.
  3. Step 3: Second iteration (i=2, node_val=7)

    top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.
  4. Step 4: Third iteration (i=1, node_val=15)

    top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.
  5. Final Answer:

    Option D -> Option D
  6. Quick Check:

    inorder_index decremented twice after popping 7 and 20 [OK]
Hint: inorder_index decrements only when popping matching nodes [OK]
Common Mistakes:
  • Off-by-one error in inorder_index update
  • Confusing when to pop stack
  • Misreading top.val vs inorder[inorder_index]
2. Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list? Tree structure: 5 / \ 4 8 / / \ 11 13 4 Target sum: 7
def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if not node.left and not node.right:
            if current_sum == targetSum:
                res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res
easy
A. []
B. [[5, 4, 11]]
C. [[5, 4]]
D. [[5, 8, 4]]

Solution

  1. Step 1: Trace paths and sums

    Paths: 5->4->11 sum=20, 5->8->13 sum=26, 5->8->4 sum=17; none equals 7.
  2. Step 2: Confirm no leaf path sums to 7

    Since no leaf path sums to 7, result list remains empty.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    No leaf path sums to 7, so empty list returned [OK]
Hint: Check sums only at leaf nodes [OK]
Common Mistakes:
  • Confusing intermediate node sums with leaf sums
  • Forgetting to check leaf condition
3. 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
4. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?
def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if current_sum == targetSum:
            res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res
medium
A. Line appending left child to stack
B. Line initializing stack with root node and path
C. Line appending right child to stack
D. Line checking if current_sum == targetSum without verifying leaf node

Solution

  1. Step 1: Identify condition for adding path to results

    Correct code adds path only if current node is leaf and sum matches.
  2. Step 2: Locate bug

    Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Missing leaf check causes incorrect paths in results [OK]
Hint: Always check leaf node before adding path [OK]
Common Mistakes:
  • Adding path before confirming leaf node
  • Forgetting to backtrack in recursion
5. Consider the following buggy deserialization code snippet for BFS-based tree reconstruction. Which line contains the subtle bug that causes incorrect tree structure when deserializing?
def deserialize(data):
    if not data:
        return None
    vals = data.split(',')
    root = TreeNode(int(vals[0]))
    queue = deque([root])
    i = 1
    while queue:
        node = queue.popleft()
        if vals[i] != 'X':
            node.left = TreeNode(int(vals[i]))
            queue.append(node.left)
        i += 1
        if vals[i] != 'X':
            node.right = TreeNode(int(vals[i]))
            queue.append(node.right)
        i += 1
    return root
medium
A. Line: if vals[i] != 'X': (left child check)
B. Line: i += 1 (after left child assignment)
C. Line: if vals[i] != 'X': (right child check)
D. Line: while queue: (loop condition)

Solution

  1. Step 1: Identify potential infinite loop

    The loop condition 'while queue:' does not check if 'i' has exceeded vals length, risking index out of range or infinite loop.
  2. Step 2: Understand impact on deserialization

    Without checking 'i < len(vals)', the loop may continue after all nodes processed, causing errors or incorrect tree structure.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]
Hint: Loop must check index bounds to avoid infinite loops [OK]
Common Mistakes:
  • Not checking index bounds in deserialization loops
  • Mixing up left and right child assignments
  • Forgetting to append children to queue
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard