Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftGoogle

Symmetric Tree (DFS Approach)

Choose your preparation mode4 modes available
▶
Steps
setup

Start isSymmetric with root node

The algorithm begins by checking if the root is null. Since root exists, it proceeds to call isMirror on root's left and right children (nodes with value 2).

💡 This step sets up the initial recursive comparison between the left and right subtrees of the root.
Line:return isMirror(root.left, root.right) if root else True
💡 The symmetry check starts by comparing the two main subtrees of the root.
📊
Symmetric Tree (DFS Approach) - Watch the Algorithm Execute, Step by Step
Watching each recursive call and comparison helps you understand how the algorithm checks mirror symmetry by comparing corresponding nodes in left and right subtrees.
Step 1/16
·Active fill★Answer cell
Current node: 2
1223443
DFS Stack
2 (entered)t1=2 t2=31 (entered)
Current node: 2
1223443
DFS Stack
2 (entered)t1=2 t2=31 (entered)
Current node: 2
1223443
DFS Stack
2 (entered)t1=2 t2=31 (entered)
Current node: 4
1223443
DFS Stack
4 (entered)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)
Current node: 4
1223443
DFS Stack
4 (entered)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)
Current node: 4
1223443
DFS Stack
4 (entered)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)
1223443
DFS Stack
4 (left_done)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)
Return: true
1223443
DFS Stack
4 (right_done)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)
Return: true
Current node: 2
1223443
DFS Stack
2 (right_done)t1=2 t2=31 (entered)
Return: true
Current node: 5
1223443
DFS Stack
2 (entered)t1=5 t2=61 (entered)
Current node: 5
1223443
DFS Stack
2 (entered)t1=5 t2=61 (entered)
Current node: 5
1223443
DFS Stack
2 (entered)t1=5 t2=61 (entered)
1223443
DFS Stack
5 (entered)t1=null t2=null2 (entered)t1=5 t2=61 (entered)
Return: true
1223443
DFS Stack
5 (right_done)t1=null t2=null2 (entered)t1=5 t2=61 (entered)
Return: true
Current node: 1
1223443
DFS Stack
1 (entered)
Return: true
1223443
Return: true

Key Takeaways

✓ The algorithm checks symmetry by recursively comparing mirrored pairs of nodes from left and right subtrees.

This insight is hard to see from code alone because the recursion intertwines two subtrees simultaneously.

✓ Early exits occur when one node is null and the other is not, or when node values differ, preventing unnecessary recursion.

Visualizing these early exits clarifies how the algorithm efficiently detects asymmetry.

✓ The final answer is true only if all mirrored node pairs are symmetric, demonstrated by the recursive returns bubbling up true.

Seeing the recursive returns helps understand how local symmetry checks combine into a global result.

Practice

(1/5)
1. Consider the following iterative postorder traversal code to compute the diameter of a binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final value of the variable diameter after the function completes?
easy
A. 2
B. 4
C. 1
D. 3

Solution

  1. Step 1: Trace heights and diameter updates for each node.

    Node 4: height=1, diameter=0; Node 2: left=1 (node4), right=0, diameter=max(0,1)=1; Node 3: height=1, diameter=1; Node 1: left=2 (node2), right=1 (node3), diameter=max(1,2+1=3)=3.
  2. Step 2: Verify final diameter value returned.

    The diameter is the maximum sum of left and right heights at any node, which is 3 edges, so the longest path length is 3 edges.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Longest path is from node 4 to node 3 with length 3 edges [OK]
Hint: Diameter counts edges, not nodes [OK]
Common Mistakes:
  • Confusing diameter as number of nodes
  • Off-by-one in height calculation
  • Missing right subtree height
2. What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?
medium
A. O(n log n) because each node is visited multiple times during threading
B. O(n) but with O(n) auxiliary space due to recursion stack
C. O(n^2) because the inner loop to find predecessor can traverse many nodes repeatedly
D. O(n) because each edge is traversed at most twice during threading and restoration

Solution

  1. Step 1: Identify traversal of nodes and edges

    Each node is visited once, and each edge is traversed at most twice (once to create thread, once to remove it).
  2. Step 2: Explain why complexity is linear

    Because total edge traversals sum to O(n), the overall time complexity is O(n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Threading and restoring links cause at most two visits per edge [OK]
Hint: Each edge visited max twice -> O(n) time [OK]
Common Mistakes:
  • Assuming inner loop causes O(n^2)
  • Confusing threading with recursion stack space
  • Thinking threading causes log n overhead
3. Consider the following buggy code for inverting a binary tree. Which line contains the subtle bug that causes incorrect inversion?
medium
A. Line 3: Swapping children before recursive calls
B. Line 5: Recursive call on right child
C. Line 4: Recursive call on left child
D. Line 2: Missing check for empty tree

Solution

  1. Step 1: Analyze order of operations

    The code swaps children before recursively inverting subtrees, which means subtrees are swapped but not inverted themselves.
  2. Step 2: Identify why swapping before recursion is incorrect

    Swapping first causes recursion to invert the wrong subtrees, leading to partial or incorrect inversion.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Swapping must happen after recursive calls to invert subtrees correctly [OK]
Hint: Swap after recursion, not before, to invert subtrees properly [OK]
Common Mistakes:
  • Swapping children before recursion
  • Ignoring null root checks
  • Confusing left and right subtree recursion order
4. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?
hard
A. Use Morris traversal by creating threads on parent pointers instead of child pointers.
B. Use breadth-first search since parent pointers allow level order traversal.
C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.
D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

  1. Step 1: Understand traversal constraints

    Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
  2. Step 2: Use parent pointers to simulate traversal

    By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Tracking previous node enables correct traversal without extra space [OK]
Hint: Parent pointers + prev node tracking enable traversal [OK]
Common Mistakes:
  • Trying to create threads on parent pointers
  • Using recursion without child pointers
  • Confusing BFS with inorder traversal
5. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?
hard
A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.
B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.
C. Switch to preorder and inorder traversals which do not have duplicates.
D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

  1. Step 1: Understand the impact of duplicates

    Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.
  2. Step 2: Required modification

    Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.
  3. Step 3: Why other options fail

    Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking multiple indices per value is necessary for duplicates [OK]
Hint: Duplicates require tracking all indices, not just one [OK]
Common Mistakes:
  • Ignoring duplicates in hash map
  • Assuming unique values always
  • Switching traversal types incorrectly
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