Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoft

Binary Tree Preorder Traversal

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize current to root and result to empty

Set current node to root (value 1) and initialize an empty list to store traversal result.

💡 Starting point: current points to root, no nodes visited yet.
Line:result = [] current = root
💡 Traversal begins at root; result list is ready to collect node values.
📊
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

  1. 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).
  2. 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).
  3. Step 3: Calculate rob_current at root (value 3)

    rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Sum matches known example output 7 [OK]
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

  1. Step 1: Trace path 1->2

    current_number accumulates 1 then 12; leaf node 2 adds 12 to total.
  2. 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.
  3. Step 3: Check for off-by-one or missed increments

    Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.
  4. Final Answer:

    Option C -> Option C
  5. 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

  1. Step 1: Analyze main loops

    The algorithm iterates preorder once, pushing and popping nodes from stack at most once each.
  2. Step 2: Consider hash map lookups

    Hash map lookups for inorder indices are O(1) each, so no extra log factor.
  3. Final Answer:

    Option C -> Option C
  4. 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

  1. 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.
  2. Step 2: Confirm no auxiliary data structures

    Only constant extra variables (pointers and counters) are used, so space complexity is O(1).
  3. Final Answer:

    Option A -> Option A
  4. 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

  1. Step 1: Recognize diameter depends on path length (edges), not node values.

    Negative values do not affect height or path length calculations.
  2. Step 2: Confirm standard height-based diameter algorithm works unchanged.

    Heights and diameter calculations rely on structure, so no changes are needed.
  3. Final Answer:

    Option A -> Option A
  4. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard