💡 Root node identified and stack initialized to manage subtree construction.
fill_cells
Process next postorder element: 20
Create a new node with value 20 from postorder[-2]. Compare top of stack (3) with inorder[inorder_index] (7). Since 3 != 7, attach 20 as right child of 3 and push 20 onto stack.
💡 This step shows how right children are attached when the top of stack does not match inorder at current index.
Line:node_val = postorder[i]
node = TreeNode(node_val)
top = stack[-1]
if top.val != inorder[inorder_index]:
top.right = node
stack.append(node)
💡 Right subtree nodes are added first when inorder and stack top differ.
fill_cells
Process next postorder element: 7
Create node 7 from postorder[-3]. Top of stack is 20, which is not equal to inorder[inorder_index] (7). Attach 7 as right child of 20 and push 7 onto stack.
💡 Continuing to add right children as long as top of stack differs from inorder at current index.
Line:node_val = postorder[i]
node = TreeNode(node_val)
top = stack[-1]
if top.val != inorder[inorder_index]:
top.right = node
stack.append(node)
💡 Right subtree is extended deeper before backtracking.
compare
Process next postorder element: 15
Create node 15 from postorder[-4]. Now top of stack is 7, which equals inorder[inorder_index] (7). Begin popping from stack while top matches inorder at inorder_index.
💡 This step shows the key backtracking: when top of stack matches inorder, we pop to move left in the tree.
Line:while stack and stack[-1].val == inorder[inorder_index]:
top = stack.pop()
inorder_index -= 1
💡 Matching inorder values indicate completed right subtree; time to attach left child.
compare
Continue popping stack for inorder match
Top of stack is now 20, which equals inorder[inorder_index] (20). Pop 20 and decrement inorder_index to 2.
💡 Continuing to pop stack nodes that match inorder to backtrack correctly.
Line:while stack and stack[-1].val == inorder[inorder_index]:
top = stack.pop()
inorder_index -= 1
💡 Backtracking continues until top of stack no longer matches inorder.
fill_cells
Attach 15 as left child of 20
After popping, top of stack is 3 which does not equal inorder[inorder_index] (15). Attach 15 as left child of last popped node (20) and push 15 onto stack.
💡 This step attaches a left child after backtracking, showing how left subtrees are built.
Line:top.left = node
stack.append(node)
💡 Left children are attached after popping nodes matching inorder.
fill_cells
Process next postorder element: 9
Create node 9 from postorder[-5]. Top of stack is 15, which equals inorder[inorder_index] (15). Begin popping from stack while top matches inorder at inorder_index.
💡 This step shows the key backtracking again: when top of stack matches inorder, pop to move left in the tree.
Line:while stack and stack[-1].val == inorder[inorder_index]:
top = stack.pop()
inorder_index -= 1
💡 Correctly identifying when to pop stack nodes to attach left children is crucial for accurate tree reconstruction.
fill_cells
Pop stack and attach 9 as left child
Attach 9 as left child of last popped node (15) and push 9 onto stack.
💡 This step shows attaching left child after popping nodes matching inorder.
Line:top.left = node
stack.append(node)
💡 Left children are attached after backtracking from matching inorder nodes.
compare
Pop stack and attach left subtree complete
Top of stack is 9, which equals inorder[inorder_index] (9). Pop 9 and decrement inorder_index to 1. Then top is 3, which equals inorder[inorder_index] (3). Pop 3 and decrement inorder_index to -1.
💡 Final backtracking steps to complete tree construction.
Line:while stack and stack[-1].val == inorder[inorder_index]:
top = stack.pop()
inorder_index -= 1
💡 Backtracking finishes when all inorder nodes matched and popped.
reconstruct
Return constructed tree root
All nodes processed and stack is empty. Return the root node (3) which now has left and right subtrees attached correctly.
💡 This final step confirms the tree is fully constructed and ready for use.
Line:return root
💡 The root node represents the fully reconstructed binary tree.
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(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder or not postorder:
return None
stack = [] # STEP 1
root_val = postorder[-1] # STEP 1
root = TreeNode(root_val) # STEP 1
stack.append(root) # STEP 1
inorder_index = len(inorder) - 1 # STEP 1
for i in range(len(postorder) - 2, -1, -1): # STEP 2 to 9
node_val = postorder[i] # STEP 2
node = TreeNode(node_val) # STEP 2
top = stack[-1] # STEP 2
if top.val != inorder[inorder_index]: # STEP 2,3
top.right = node # STEP 2,3
stack.append(node) # STEP 2,3
else:
while stack and stack[-1].val == inorder[inorder_index]: # STEP 4,5,9
top = stack.pop() # STEP 4,5,9
inorder_index -= 1 # STEP 4,5,9
top.left = node # STEP 6,8
stack.append(node) # STEP 6,8
return root # STEP 10
📊
Construct Tree from Inorder and Postorder - Watch the Algorithm Execute, Step by Step
Watching this step-by-step reveals how the stack helps reconstruct the tree without recursion, clarifying the relationship between inorder and postorder traversals.
Step 1/10
·Active fill★Answer cell
Current node: 0
3
Current node: 1
320
Current node: 2
3207
Current node: 3
320715
Current node: 3
320715
Current node: 3
320715
Current node: 4
3207159
Current node: 4
3207159
3207159
Current node: 0
3207159
Return: 0
Key Takeaways
✓ The last element in postorder is always the root, which anchors the entire tree construction.
This is fundamental but often overlooked; seeing it visually helps cement this root identification.
✓ The stack tracks nodes whose subtrees are not fully constructed, enabling iterative backtracking instead of recursion.
Understanding how the stack simulates recursion clarifies the algorithm's flow and why nodes are popped when inorder matches.
✓ When the top of the stack matches the current inorder element, it signals completion of the right subtree and triggers attaching left children.
This decision point is subtle in code but critical; the visualization makes it explicit and easy to follow.
Practice
(1/5)
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
Step 1: Understand the problem constraints
The problem requires checking balance at every node efficiently without recomputing heights multiple times.
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.
Final Answer:
Option D -> Option D
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. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current # create thread
current = current.left
else:
# BUG: missing line to remove thread
result.append(current.val)
current = current.right
return result
medium
A. Missing line resetting predecessor.right = None to remove thread
B. Line moving current to current.left after creating thread
C. Line appending current.val after detecting thread
D. Line setting predecessor.right = current (creating thread)
Solution
Step 1: Identify thread removal step
Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
Step 2: Locate missing removal
The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
Final Answer:
Option A -> Option A
Quick Check:
Without removing thread, traversal loops endlessly [OK]
Hint: Always remove threads to restore tree [OK]
Common Mistakes:
Forgetting to remove thread
Appending node before removing thread
Incorrectly creating thread
3. Consider the following buggy code snippet for building a binary tree from preorder and inorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or infinite loops?
medium
A. Line where stack is initialized with root
B. Line inside if block missing stack.append(node.left)
C. Line where root is initialized with preorder[0]
D. Line inside else block where inorder_index is incremented
Solution
Step 1: Identify missing operation
Inside the if block, after creating node.left, the new node is not pushed onto the stack.
Step 2: Consequences of missing stack append
Without pushing, the algorithm loses track of the left subtree root, causing incorrect tree or infinite loops.
Final Answer:
Option B -> Option B
Quick Check:
Stack must track all nodes to correctly build tree [OK]
Hint: Always push newly created nodes to stack to track subtree roots [OK]
Common Mistakes:
Forgetting to push left child nodes
Incorrectly incrementing inorder_index
Misinitializing root or stack
4. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?
medium
A. O(n^2) due to checking grandchildren nodes explicitly
B. O(n) but with extra O(n) space for memoization arrays
C. O(n) because each node is visited once in DFS
D. O(n log n) because of recursive calls and combining results
Solution
Step 1: Identify DFS traversal cost
The algorithm visits each node exactly once in a postorder DFS traversal.
Step 2: Analyze operations per node
At each node, constant time operations are done: combining left and right child results, no repeated work.
Final Answer:
Option C -> Option C
Quick Check:
Linear traversal of n nodes -> O(n) time [OK]
Hint: DFS visits each node once, no repeated subproblems [OK]
Common Mistakes:
Assuming O(n^2) due to grandchildren checks
Confusing recursion stack space with time complexity
5. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.
def lowestCommonAncestor(root, p, q):
parent = {root: None}
stack = [root]
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q
medium
A. Line: while p not in parent or q not in parent:
B. Line: while p:
C. Line: while q not in ancestors:
D. Line: parent = {root: None}
Solution
Step 1: Analyze parent map construction loop
The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.
Step 2: Identify subtle bug
If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.
Step 3: Explanation
The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.
Final Answer:
Option A -> Option A
Quick Check:
Loop condition must ensure both nodes are in parent map to avoid errors [OK]
Hint: Parent map construction loop must fully process both nodes [OK]
Common Mistakes:
Assuming parent map always complete
Ignoring incomplete parent map causing KeyError
Misplacing bug in ancestor set loops
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.