💡 Removing thread restores original tree structure.
traverse
Move current to right child of node 2
After removing the thread, move current to the right child of node 2, which is null.
💡 Moving to right child continues traversal after left subtree is done.
Line:current = current.right
💡 Traversal proceeds to right subtree or ends if null.
traverse
Current is null, traversal complete
Current node is null, indicating traversal is complete and all nodes have been visited.
💡 Traversal ends when there are no more nodes to visit.
Line:while current:
...
return result
💡 Algorithm successfully visited all nodes in preorder without recursion or stack.
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 preorderTraversal(root: Optional[TreeNode]) -> List[int]:
result = [] # STEP 1: Initialize result list
current = root # STEP 1: Start at root
while current: # STEP 9: Loop until current is None
if current.left is None: # STEP 2 & 6: No left child, visit and move right
result.append(current.val) # STEP 2 & 6: Visit current
current = current.right # STEP 2 & 6: Move to right child
else:
predecessor = current.left # STEP 3: Find predecessor
while predecessor.right and predecessor.right != current: # STEP 4: Move to rightmost
predecessor = predecessor.right
if predecessor.right is None: # STEP 5: Create thread and visit
predecessor.right = current
result.append(current.val)
current = current.left
else: # STEP 7 & 8: Thread exists, remove and move right
predecessor.right = None
current = current.right
return result # STEP 9: Return final preorder list
📊
Binary Tree Preorder Traversal - Watch the Algorithm Execute, Step by Step
Watching each step reveals how the algorithm cleverly uses tree threading to avoid extra space, making preorder traversal efficient and elegant.
Step 1/9
·Active fill★Answer cell
Current node: 1
123
Current node: 2
123
Result: [1]
Current node: 2
123
DFS Stack
2 (entered)predecessor=3
Result: [1]
Current node: 2
123
DFS Stack
2 (entered)predecessor=3
Result: [1]
Current node: 3
123
DFS Stack
2 (left_done)predecessor=3
Result: [1, 2]
Current node: 2
123
Result: [1, 2, 3]
Current node: 2
123
Result: [1, 2, 3]
123
Result: [1, 2, 3]
123
Result: [1, 2, 3]
Return: [1,2,3]
Key Takeaways
✓ Morris traversal uses temporary threads to traverse the tree without recursion or stack.
This insight is hard to see from code alone because the pointer changes are subtle and temporary.
✓ Nodes are visited before traversing left subtree, matching preorder order exactly.
Visualizing the visit order clarifies why the algorithm appends node values at specific steps.
✓ Threads are created and removed dynamically to simulate recursion return points.
Seeing when and why threads are added or removed helps understand the traversal flow control.
Practice
(1/5)
1. Consider the following code implementing the optimal House Robber III solution. Given the tree:
3
/ \
2 3
\ \
3 1
What is the value of rob_current when dfs is called on the root node (value 3)?
easy
A. 7
B. 6
C. 8
D. 9
Solution
Step 1: Trace dfs on left child (value 2)
dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).
Step 2: Trace dfs on right child (value 3)
dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).
Hint: Add node.val + not_rob of children for rob_current [OK]
Common Mistakes:
Mixing rob and not_rob values for children
Off-by-one in recursion returns
2. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree:
1
/ \
2 3
What is the final value of the variable total returned by sumNumbers?
easy
A. 5
B. 15
C. 25
D. 26
Solution
Step 1: Trace path 1->2
current_number accumulates 1 then 12; leaf node 2 adds 12 to total.
Step 2: Trace path 1->3
current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.
Step 3: Check for off-by-one or missed increments
Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.
Final Answer:
Option C -> Option C
Quick Check:
Sum of 12 and 13 is 25, matching code behavior [OK]
Hint: Trace current_number updates carefully at each node [OK]
Common Mistakes:
Off-by-one in current_number division
Adding non-leaf nodes to total
3. What is the time complexity of the optimized iterative approach using a stack and a hash map to build a binary tree from preorder and inorder traversals of length n?
medium
A. O(n^2) due to nested loops scanning preorder and inorder arrays
B. O(n log n) due to hash map lookups for inorder indices
C. O(n) because each node is pushed and popped at most once from the stack
D. O(n) but with O(n^2) auxiliary space for recursion stack
Solution
Step 1: Analyze main loops
The algorithm iterates preorder once, pushing and popping nodes from stack at most once each.
Step 2: Consider hash map lookups
Hash map lookups for inorder indices are O(1) each, so no extra log factor.
Final Answer:
Option C -> Option C
Quick Check:
Each node processed once with O(1) operations [OK]
Hint: Each node pushed and popped once; hash map lookups O(1) [OK]
Common Mistakes:
Assuming nested loops cause O(n^2)
Confusing hash map lookup cost
Counting recursion stack space in iterative approach
4. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?
medium
A. O(1) because Morris traversal uses threaded binary tree links without extra stack
B. O(n) due to recursion stack in DFS
C. O(h) where h is tree height due to implicit stack usage
D. O(n) because all nodes are visited and stored temporarily
Solution
Step 1: Identify space usage in Morris traversal
Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.
Step 2: Confirm no auxiliary data structures
Only constant extra variables (pointers and counters) are used, so space complexity is O(1).
Final Answer:
Option A -> Option A
Quick Check:
Morris traversal is known for O(1) space by threading tree [OK]
Hint: Morris traversal avoids recursion and stack [OK]
Common Mistakes:
Confusing recursion stack with Morris traversal
Assuming O(h) due to tree height
5. Suppose the binary tree nodes can have negative values and you want to find the diameter defined as the longest path in terms of number of edges (ignoring node values). Which modification to the standard diameter algorithm is necessary to handle this variant correctly?
hard
A. No modification needed; the standard diameter algorithm based on heights works regardless of node values.
B. Modify the algorithm to sum node values along paths and find maximum sum path instead of longest path.
C. Change the height calculation to ignore negative nodes by treating them as null nodes.
D. Use breadth-first search to find the longest path instead of depth-first traversal.
Solution
Step 1: Recognize diameter depends on path length (edges), not node values.
Negative values do not affect height or path length calculations.
Step 2: Confirm standard height-based diameter algorithm works unchanged.
Heights and diameter calculations rely on structure, so no changes are needed.
Final Answer:
Option A -> Option A
Quick Check:
Diameter depends on edges, not node values [OK]
Hint: Diameter is structural, unaffected by node values [OK]
Common Mistakes:
Confusing diameter with max sum path
Ignoring negative nodes incorrectly
Switching to BFS unnecessarily
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.