Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftGoogle

Binary Tree Inorder Traversal

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize current to root

Set current pointer to the root node (value 1). The result list is empty at this point.

💡 Starting at the root is essential to begin traversal from the top of the tree.
Line:result = [] current = root
💡 The traversal begins at the root node with no nodes visited yet.
📊
Binary Tree Inorder Traversal - Watch the Algorithm Execute, Step by Step
Watching each step shows how the algorithm cleverly creates and removes threads to traverse the tree in order without extra space.
Step 1/10
·Active fill★Answer cell
Current node: 1
123
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 (left_done)predecessor=3
Result: [1]
Current node: 3
123
DFS Stack
2 (left_done)predecessor=3
Result: [1]
Current node: 2
123
DFS Stack
2 (left_done)predecessor=3
Result: [1, 3]
123
Result: [1, 3, 2]
123
Result: [1, 3, 2]
123
Result: [1, 3, 2]
Return: [1,3,2]

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 thread creation and removal are subtle and happen dynamically.

✓ Nodes without left children are visited immediately, simplifying traversal steps.

Understanding this helps learners see why some nodes are visited right away and others require threading.

✓ Thread removal signals completion of left subtree traversal and triggers visiting the current node.

This concrete example clarifies the key decision point where traversal switches from left subtree to root.

Practice

(1/5)
1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy
A. 2
B. 0
C. 3
D. 1

Solution

  1. Step 1: Trace dfs on leaf nodes 1 and 2

    Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.
  2. Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here

    Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    One camera at root covers all nodes [OK]
Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
  • Counting cameras on leaves instead of parent
  • Forgetting to add camera at root if uncovered
  • Misinterpreting coverage states
2. You need to output all nodes of a binary tree such that each node is processed only after its left and right children have been processed. Which traversal approach guarantees this order?
easy
A. Postorder traversal using depth-first search
B. Preorder traversal using recursion
C. Level-order traversal using a queue
D. Inorder traversal using recursion

Solution

  1. Step 1: Understand traversal order requirements

    Postorder traversal processes left subtree, then right subtree, then the node itself, ensuring children are processed before the parent.
  2. Step 2: Compare with other traversals

    Preorder and inorder do not guarantee children processed before parent; level-order processes nodes by depth, not child-first.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder traversal matches the problem's processing order [OK]
Hint: Postorder processes children before parent [OK]
Common Mistakes:
  • Confusing inorder with postorder
  • Thinking preorder processes children first
3. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?
easy
A. 4
B. 3
C. 5
D. 6

Solution

  1. Step 1: Calculate tree height

    Height h = 3 (nodes 1 -> 2 -> 4).
  2. Step 2: Binary search on last level nodes

    Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
Hint: Count = perfect nodes + last level nodes found [OK]
Common Mistakes:
  • Off-by-one in binary search bounds
  • Miscounting last level nodes
4. You are given a binary tree and asked to transform it into a singly linked list in-place such that the linked list follows the preorder traversal of the tree. Which approach guarantees an optimal solution with O(n) time and O(h) space complexity, where h is the tree height?
easy
A. Use a reverse preorder traversal (right subtree first, then left) with a global pointer to rewire nodes in-place.
B. Perform a preorder traversal, store nodes in a list, then rebuild the linked list from the list.
C. Use a bottom-up postorder traversal to reconstruct the linked list from leaves to root.
D. Apply a greedy approach that always attaches the left subtree to the rightmost node of the right subtree.

Solution

  1. Step 1: Understand traversal order needed

    The linked list must follow preorder traversal (root, left, right).
  2. Step 2: Identify approach that rewires in-place efficiently

    Reverse preorder traversal (right, left) with a global pointer allows rewiring nodes in-place without extra storage, achieving O(n) time and O(h) space due to recursion stack.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Reverse preorder traversal with global pointer rewires nodes in correct order [OK]
Hint: Reverse preorder traversal with global pointer is optimal [OK]
Common Mistakes:
  • Using extra space to store nodes before rebuilding
  • Confusing traversal order causing incorrect linked list
  • Trying greedy rewiring without correct traversal order
5. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?
medium
A. Line creating root node with postorder[-1]
B. Line initializing inorder_index to 0
C. Line attaching node as right child
D. Line popping from stack inside while loop

Solution

  1. Step 1: Identify inorder_index initialization

    inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.
  2. Step 2: Consequences of wrong initialization

    Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Correct inorder_index initialization is critical for stack popping logic [OK]
Hint: inorder_index must start at last index, not zero [OK]
Common Mistakes:
  • Wrong inorder_index initialization
  • Confusing postorder traversal direction
  • Incorrect stack popping conditions
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