💡 These variables track the traversal progress: stack for nodes to revisit, current for exploration, and last_visited to avoid revisiting right subtrees.
fill_cells
Push current node (1) and move left
Current node 1 is pushed onto the stack. Since it has no left child, current moves to None.
💡 Pushing nodes while moving left simulates recursive calls going down the left subtree.
Line:while current:
stack.append(current)
current = current.left
💡 We push node 1 to revisit it after its left subtree is processed.
compare
Peek top node (1) and check right child
Peek at the top of the stack, node 1. It has a right child (node 2) that has not been visited yet, so we set current to node 2 to traverse its subtree.
💡 Checking the right child ensures we traverse right subtrees before visiting the node itself.
Line:peek_node = stack[-1]
if peek_node.right and last_visited != peek_node.right:
current = peek_node.right
💡 We delay visiting node 1 until its right subtree is fully traversed.
fill_cells
Push current node (2) and move left
Current node 2 is pushed onto the stack. We move current to its left child, node 3, to continue traversing left.
💡 Continuing to push left children simulates recursive descent down the left subtree.
Line:while current:
stack.append(current)
current = current.left
💡 Node 2 is now on the stack waiting for its left subtree to be processed.
fill_cells
Push current node (3) and move left (None)
Current node 3 is pushed onto the stack. It has no left child, so current moves to None.
💡 Leaf nodes are pushed and then current becomes None, triggering the visit or right subtree check.
Line:while current:
stack.append(current)
current = current.left
💡 Node 3 is now the top of the stack, ready to be visited or to check right subtree.
compare
Peek top node (3), no right child, visit node
Peek at node 3 on top of the stack. It has no right child, so we visit it by appending its value to result and pop it from the stack.
💡 Visiting nodes happens only after left and right subtrees are fully processed.
Line:peek_node = stack[-1]
if peek_node.right and last_visited != peek_node.right:
current = peek_node.right
else:
result.append(peek_node.val)
last_visited = stack.pop()
💡 Node 3 is the leftmost leaf and is visited first in postorder.
compare
Peek top node (2), no right child unvisited, visit node
Peek at node 2 on top of the stack. It has no right child unvisited (right is None), so we visit node 2 and pop it from the stack.
💡 After left subtree is visited, if no right subtree exists or is visited, we visit the node itself.
Line:peek_node = stack[-1]
if peek_node.right and last_visited != peek_node.right:
current = peek_node.right
else:
result.append(peek_node.val)
last_visited = stack.pop()
💡 Node 2 is visited after its left subtree (node 3) is done.
compare
Peek top node (1), right child visited, visit node
Peek at node 1 on top of the stack. Its right child (node 2) was last visited, so we visit node 1 and pop it from the stack.
💡 We visit the root node only after both left and right subtrees are fully visited.
Line:peek_node = stack[-1]
if peek_node.right and last_visited != peek_node.right:
current = peek_node.right
else:
result.append(peek_node.val)
last_visited = stack.pop()
💡 Node 1 is visited last, completing the postorder traversal.
reconstruct
Traversal complete, return result
Stack is empty and current is None, so traversal is complete. The result list [3, 2, 1] is returned as the postorder traversal.
💡 Returning the result finalizes the traversal and provides the output.
Line:return result
💡 The traversal order matches the expected postorder sequence.
summary
Summary and final notes
The iterative postorder traversal is complete. The stack is empty, and the result contains the nodes in postorder: left subtree, right subtree, then root.
💡 This final step reinforces the traversal order and the role of the stack and last_visited pointer.
💡 Understanding the stack and last_visited pointer is key to mastering iterative postorder traversal.
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 postorderTraversal(root: Optional[TreeNode]) -> List[int]:
result = [] # STEP 1: Initialize result list
stack = [] # STEP 1: Initialize empty stack
last_visited = None # STEP 1: Track last visited node
current = root # STEP 1: Start from root
while current or stack: # STEP 2: Continue while nodes remain
while current: # STEP 4: Traverse left subtree
stack.append(current) # STEP 4: Push current node
current = current.left # STEP 4: Move left
peek_node = stack[-1] # STEP 6: Peek top node
if peek_node.right and last_visited != peek_node.right: # STEP 7: Check right child
current = peek_node.right # STEP 7: Move to right child
else:
result.append(peek_node.val) # STEP 8: Visit node
last_visited = stack.pop() # STEP 8: Pop node
return result # STEP 9: Return final traversal result
📊
Binary Tree Postorder Traversal - Watch the Algorithm Execute, Step by Step
Watching each step of the traversal helps you understand how the algorithm simulates recursion using a stack and tracks last visited nodes to decide when to visit or traverse right subtrees.
Step 1/10
·Active fill★Answer cell
Current node: 1
123
123
DFS Stack
1 (entered)
Current node: 2
123
DFS Stack
1 (left_done)
Current node: 3
123
DFS Stack
2 (entered)1 (left_done)
123
DFS Stack
3 (entered)2 (entered)1 (left_done)
123
DFS Stack
2 (entered)1 (left_done)
Result: [3]
123
DFS Stack
1 (left_done)
Result: [3, 2]
123
Result: [3, 2, 1]
123
Result: [3, 2, 1]
Return: [3,2,1]
123
Result: [3, 2, 1]
Return: [3,2,1]
Key Takeaways
✓ The algorithm uses a stack and a last_visited pointer to simulate recursion and ensure nodes are visited after their subtrees.
This insight is hard to see from code alone because the interplay between stack and last_visited is subtle and critical for correct postorder.
✓ Nodes are pushed while traversing left, and only visited after both left and right subtrees are processed.
Visualizing the stack growing and shrinking clarifies the traversal order dependency.
✓ The decision to move to the right child or visit the node depends on whether the right subtree has been visited, tracked by last_visited.
Seeing this decision in action helps understand why the algorithm avoids revisiting nodes prematurely.
Practice
(1/5)
1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?
easy
A. Use a breadth-first search (BFS) to visit nodes level by level.
B. Use a recursive preorder traversal that visits root, left, then right nodes.
C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.
D. Use a dynamic programming approach to store and reuse subtree results.
Solution
Step 1: Understand traversal order requirement
Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
Step 2: Identify approach with O(1) space
Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.
Final Answer:
Option C -> Option C
Quick Check:
Morris traversal is known for O(1) space inorder traversal [OK]
Hint: Morris traversal enables inorder with O(1) space [OK]
Common Mistakes:
Confusing preorder with inorder traversal order
Assuming BFS can produce inorder sequence
Thinking DP applies to traversal order
2. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below?
Tree structure:
1
/ \
2 3
def preorderTraversal(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
result.append(current.val)
current = current.left
else:
predecessor.right = None
current = current.right
return result
easy
A. [2, 1, 3]
B. [1, 2, 3]
C. [1, 3, 2]
D. [3, 1, 2]
Solution
Step 1: Trace first iteration with current=1
Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.
Step 2: Trace second iteration with current=2
Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).
Step 3: Detect thread at 2.right=1
Since predecessor.right == current, reset 2.right=None, move current=1.right=3.
Step 4: Trace current=3
Node 3 has no left child, append 3, move current=3.right=None, loop ends.
Final Answer:
Option B -> Option B
Quick Check:
Output matches preorder traversal [1,2,3] [OK]
Hint: Morris preorder appends root before left subtree [OK]
Common Mistakes:
Appending nodes in wrong order
Not resetting threaded links
Confusing left and right child traversal
3. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?
medium
A. O(n) due to storing all nodes in a list during traversal
B. O(1) because the algorithm modifies the tree in-place without extra memory
C. O(log n) because the tree height is always balanced and recursion stack is limited
D. O(h) due to recursion stack depth in worst case of skewed tree
Solution
Step 1: Identify auxiliary space usage
The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.
Step 2: Clarify why O(h) not O(1) or O(n)
It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.
Final Answer:
Option D -> Option D
Quick Check:
Recursion stack space equals tree height h [OK]
Hint: Recursion stack space equals tree height h [OK]
Common Mistakes:
Assuming O(1) space because of in-place modification
Confusing recursion stack with explicit data structures
Assuming balanced tree always so O(log n) space
4. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?
hard
A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.
B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.
C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.
D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.
Solution
Step 1: Understand the reuse constraint
Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.
Step 2: Identify necessary algorithmic change
We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.
Step 3: Why other options fail
Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.
Final Answer:
Option D -> Option D
Quick Check:
Memoization with extended state handles reuse and adjacency constraints [OK]
Hint: Reuse requires stateful memoization, not simple DFS [OK]
Common Mistakes:
Assuming original DFS suffices for reuse
Ignoring adjacency constraints when reusing nodes
5. Suppose the problem is modified so that node values can be negative integers, and the goal remains to sum all root-to-leaf numbers formed by concatenation (including negative signs). Which of the following changes to the algorithm is necessary to handle this correctly?
hard
A. Skip negative nodes since they break number formation
B. Continue using integer arithmetic with multiplication by 10, ignoring signs
C. Add absolute values of node.val to current_number to avoid sign issues
D. Use string concatenation of node values along the path and convert to integer at leaf nodes
Solution
Step 1: Understand impact of negative values
Integer arithmetic with multiplication by 10 assumes digits 0-9; negative signs break this assumption.
Step 2: Identify correct approach
Concatenating node values as strings preserves negative signs and digit order; convert to integer only at leaf nodes.
Step 3: Confirm other options fail
Ignoring signs or skipping negatives leads to incorrect sums or incomplete paths.