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.
💡 Root node creation anchors the tree; stack starts with root to manage child attachments.
fill_cells
Process preorder value 9: attach as left child
Look at next preorder value 9. Top of stack is node 3, which does not match inorder[inorder_index] (9). Attach 9 as left child of 3 and push it onto stack.
💡 When top of stack's value differs from inorder[inorder_index], we add left children to build left subtree.
💡 Popping signals completion of left subtree nodes and readiness to attach right children.
fill_cells
Attach 20 as right child of 3
After popping 9, top of stack is 3 which matches inorder[inorder_index] (3). Pop 3 and increment inorder_index to 2. Attach 20 as right child of 3 and push it onto stack.
💡 We continue popping while top matches inorder to find correct parent for right child.
💡 Popping signals readiness to attach right child after finishing left subtree.
fill_cells
Pop 20 and attach 7 as right child
Top of stack is 20 which matches inorder[inorder_index] (20). Pop 20 and increment inorder_index to 4. Attach 7 as right child of 20 and push it onto stack.
💡 Continue popping to find correct parent for right child 7.
💡 Right children are attached after popping nodes matching inorder to move to right subtree.
compare
Finalize construction: pop 7 and increment inorder_index
Top of stack is 7, which matches inorder[inorder_index] (7). Pop 7 and increment inorder_index to 5, which is beyond inorder length, indicating completion.
💡 Popping last node matching inorder means all nodes processed and tree construction is complete.
💡 When inorder_index reaches length, construction is complete.
reconstruct
Return the root node
All preorder nodes processed and stack is empty. Return the root node representing the fully constructed binary tree.
💡 Returning root allows traversal or other operations on the constructed tree.
Line:return root
💡 The root node now points to the entire constructed tree.
reconstruct
Final tree structure and answer
The tree is fully constructed with root 3, left child 9, and right subtree rooted at 20 with children 15 and 7. This matches the expected output.
💡 This final step confirms the tree matches preorder and inorder sequences.
💡 The constructed tree satisfies the input traversal constraints.
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
root = TreeNode(preorder[0]) # STEP 1
stack = [root] # STEP 1
inorder_index = 0 # STEP 1
for val in preorder[1:]: # STEP 2
node = stack[-1] # STEP 2
if node.val != inorder[inorder_index]: # STEP 3
node.left = TreeNode(val) # STEP 3
stack.append(node.left) # STEP 3
else:
while stack and stack[-1].val == inorder[inorder_index]: # STEP 6
node = stack.pop() # STEP 6
inorder_index += 1 # STEP 6
node.right = TreeNode(val) # STEP 7
stack.append(node.right) # STEP 7
return root # STEP 9
📊
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
Step 1: Understand problem constraints
The problem requires minimal cameras covering all nodes, where a camera covers parent, self, and children.
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.
Final Answer:
Option B -> Option B
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
Step 1: Understand binary search condition
The condition should be 'if idx <= mid' to correctly include mid index in left subtree.
Step 2: Identify impact of bug
Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.
Final Answer:
Option A -> Option A
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
Step 1: Identify condition for adding path to results
Correct code adds path only if current node is leaf and sum matches.
Step 2: Locate bug
Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.
Final Answer:
Option D -> Option D
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
Step 1: Understand reuse requirement
Allowing nodes to appear multiple times means the original nodes cannot be simply rewired in-place without duplication.
Step 2: Identify necessary modification
Cloning nodes during traversal is required to create multiple instances, preserving original tree structure and allowing duplicates.
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.
Final Answer:
Option C -> Option C
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
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.
Step 2: Generalize recursion and reversal
Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.
Step 3: Evaluate other options
Swapping only first and last or partial BFS swaps do not fully invert the tree structure.
Final Answer:
Option C -> Option C
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 unknownstrongwhile earning +1 Grip toward your certificate.