Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogleFacebook

Construct Tree from Preorder and Inorder

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize root and stack

Create the root node with the first preorder value (3) and initialize the stack with this root. Set inorder_index to 0 to track position in inorder array.

💡 The root is always the first preorder element; stack helps track nodes to attach children to.
Line:root = TreeNode(preorder[0]) stack = [root] inorder_index = 0
💡 Root node creation anchors the tree; stack starts with root to manage child attachments.
📊
Construct Tree from Preorder and Inorder - Watch the Algorithm Execute, Step by Step
Watching this step-by-step shows how preorder and inorder sequences guide tree construction, clarifying the stack's role and the order of node attachments.
Step 1/10
·Active fill★Answer cell
Current node: 0
3
Current node: 1
39
Current node: 0
39
Current node: 2
3920
Current node: 3
392015
Current node: 2
392015
Current node: 4
3920157
3920157
3920157
Return: 0
3920157
Return: 0

Key Takeaways

✓ The stack tracks nodes whose children are being attached, simulating recursion iteratively.

This insight is hard to see from code alone because the stack's role is implicit; visualization shows how it manages construction order.

✓ Comparing the top of the stack with the current inorder element determines whether to add left children or pop to add right children.

This decision is subtle in code but critical; visualization clarifies how preorder and inorder interplay guides tree shape.

✓ Incrementing inorder_index and popping nodes signals completion of left subtrees and readiness to attach right children.

Understanding when and why nodes are popped is easier when watching the stack state and inorder_index move step-by-step.

Practice

(1/5)
1. You need to place the minimum number of cameras in a binary tree so that every node is monitored. A camera at a node monitors its parent, itself, and its immediate children. Which approach guarantees an optimal solution for this problem?
easy
A. Brute force recursion trying all combinations of camera placements
B. Greedy postorder traversal using explicit states to track coverage and camera placement
C. Top-down dynamic programming with memoization based on node coverage
D. Level order traversal placing cameras on all nodes with uncovered children

Solution

  1. Step 1: Understand problem constraints

    The problem requires minimal cameras covering all nodes, where a camera covers parent, self, and children.
  2. Step 2: Evaluate approaches

    Brute force is exponential and inefficient. Level order placing cameras on all uncovered children is greedy but not minimal. Top-down DP is complex and less intuitive here. Greedy postorder with explicit states ensures children are processed before parent decisions, enabling minimal camera placement.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Postorder traversal with states is known optimal for this problem [OK]
Hint: Optimal solution uses postorder traversal with states [OK]
Common Mistakes:
  • Assuming level order greedy placement is minimal
  • Trying brute force without pruning
  • Confusing top-down DP with bottom-up greedy
2. 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
3. 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
4. Suppose the problem is modified so that the binary tree nodes can be reused multiple times in the flattened linked list (i.e., nodes can appear multiple times). Which modification to the optimal flatten algorithm is necessary to handle this correctly?
hard
A. No change needed; the current in-place reverse preorder traversal works as is.
B. Use a preorder traversal to collect nodes in a list and rebuild the linked list allowing duplicates.
C. Modify the algorithm to clone nodes during traversal to allow multiple appearances.
D. Switch to a postorder traversal to ensure all duplicates are appended after processing children.

Solution

  1. Step 1: Understand reuse requirement

    Allowing nodes to appear multiple times means the original nodes cannot be simply rewired in-place without duplication.
  2. Step 2: Identify necessary modification

    Cloning nodes during traversal is required to create multiple instances, preserving original tree structure and allowing duplicates.
  3. Step 3: Why other options fail

    No change needed; the current in-place reverse preorder traversal works as is. fails because in-place rewiring destroys original nodes. Use a preorder traversal to collect nodes in a list and rebuild the linked list allowing duplicates. collects nodes but does not clone them. Switch to a postorder traversal to ensure all duplicates are appended after processing children. traversal order does not address duplication.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Cloning nodes enables multiple appearances in flattened list [OK]
Hint: Cloning nodes is needed for multiple appearances [OK]
Common Mistakes:
  • Assuming in-place rewiring supports duplicates
  • Collecting nodes without cloning leads to lost references
  • Changing traversal order alone does not solve duplication
5. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?
hard
A. Swap only the first and last child pointers recursively, leaving others unchanged.
B. Use BFS to swap children pairwise at each level without recursion.
C. Recursively invert each child's subtree, then reverse the list of children in-place.
D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.

Solution

  1. Step 1: Understand inversion for binary tree swaps left and right children

    For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.
  2. Step 2: Generalize recursion and reversal

    Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.
  3. Step 3: Evaluate other options

    Swapping only first and last or partial BFS swaps do not fully invert the tree structure.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Recursion plus reversing children list generalizes inversion correctly [OK]
Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]
Common Mistakes:
  • Swapping only some children pairs
  • Ignoring recursion on all children
  • Using BFS without recursion for full inversion
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