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.
compare
Check if either node is null
The helper function isMirror checks if either node (t1 or t2) is null. Both nodes exist, so it proceeds to compare their values.
💡 Checking for null nodes is the base case for recursion and helps detect asymmetry early.
Line:if not t1 or not t2:
return t1 == t2
💡 Both nodes must exist to be symmetric; if one is null and the other is not, the tree is asymmetric.
compare
Compare node values
The algorithm compares the values of the two nodes (both 2). Since they are equal, it proceeds to recursively check their children in mirrored positions.
💡 Node values must match for symmetry; this check prevents unnecessary recursion if values differ.
Line:if t1.val != t2.val:
return False
💡 Matching node values are necessary for symmetry at this level.
traverse
Recurse on t1.left and t2.right
The algorithm recursively calls isMirror on t1.left (node 3) and t2.right (node 7) to check if these subtrees are mirrors.
💡 Recursion moves inward comparing left subtree's left child with right subtree's right child to check mirror symmetry.
Line:return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
💡 Symmetry requires mirrored children to be symmetric as well.
compare
Check if either node is null (t1=3, t2=3)
At nodes 3 and 3, the algorithm checks if either is null. Both exist, so it proceeds to compare their values.
💡 Base case check for null nodes is repeated at each recursive call to detect asymmetry early.
Line:if not t1 or not t2:
return t1 == t2
💡 Both nodes must be present to be symmetric.
compare
Compare node values (3 vs 3)
The values of nodes 3 and 3 are equal, so the algorithm continues to recursively check their children.
💡 Matching values confirm potential symmetry at this node pair.
Line:if t1.val != t2.val:
return False
💡 Node values must match for symmetry at every pair.
traverse
Recurse on t1.left and t2.right (both null)
The algorithm recursively calls isMirror on t1.left and t2.right, both null, which returns true immediately.
💡 Null nodes on both sides indicate symmetry at leaf level.
Line:if not t1 or not t2:
return t1 == t2
💡 Leaves with no children are symmetric by definition.
traverse
Recurse on t1.right and t2.left (both null)
The algorithm recursively calls isMirror on t1.right and t2.left, both null, returning true immediately.
💡 Both null children confirm symmetry at this leaf pair.
Line:if not t1 or not t2:
return t1 == t2
💡 Leaf nodes with no children are symmetric.
return
Return true for nodes 3 and 3
Both recursive calls for nodes 3 and 3 returned true, so isMirror returns true for this pair, confirming symmetry here.
💡 Returning true bubbles up the confirmation that these subtrees are symmetric.
Line:return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
💡 Symmetry at this node pair is confirmed by both children being symmetric.
traverse
Recurse on t1.right and t2.left (nodes 4 and 6)
The algorithm now recursively checks the other mirrored pair: t1.right (node 5 with value 4) and t2.left (node 6 with value 4).
💡 Checking the other mirrored child pair is necessary to confirm full subtree symmetry.
Line:return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
💡 Both mirrored pairs must be symmetric for the whole subtree to be symmetric.
compare
Check if either node is null (t1=4, t2=4)
The algorithm checks if either node is null. Both nodes exist, so it proceeds to compare their values.
💡 Null check is repeated at each recursive call to detect asymmetry early.
Line:if not t1 or not t2:
return t1 == t2
💡 Both nodes must be present to be symmetric.
compare
Compare node values (4 vs 4)
The values of nodes 4 and 4 are equal, so the algorithm continues to recursively check their children.
💡 Matching values confirm potential symmetry at this node pair.
Line:if t1.val != t2.val:
return False
💡 Node values must match for symmetry at every pair.
traverse
Recurse on t1.left and t2.right (both null)
The algorithm recursively calls isMirror on t1.left and t2.right, both null, returning true immediately.
💡 Null nodes on both sides indicate symmetry at leaf level.
Line:if not t1 or not t2:
return t1 == t2
💡 Leaves with no children are symmetric by definition.
traverse
Recurse on t1.right and t2.left (both null)
The algorithm recursively calls isMirror on t1.right and t2.left, both null, returning true immediately.
💡 Both null children confirm symmetry at this leaf pair.
Line:if not t1 or not t2:
return t1 == t2
💡 Leaf nodes with no children are symmetric.
return
Return true for nodes 4 and 4
Both recursive calls for nodes 4 and 4 returned true, so isMirror returns true for this pair, confirming symmetry here.
💡 Returning true bubbles up the confirmation that these subtrees are symmetric.
Line:return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
💡 Symmetry at this node pair is confirmed by both children being symmetric.
return
Return true for root's left and right subtrees
Both recursive calls for the root's left and right children returned true, so the entire tree is symmetric and the algorithm returns true.
💡 The final return confirms the entire tree is symmetric after all checks.
Line:return isMirror(root.left, root.right) if root else True
💡 The tree is symmetric if all mirrored pairs are symmetric.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSymmetric(root: Optional[TreeNode]) -> bool:
def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
# STEP 2
if not t1 or not t2:
return t1 == t2
# STEP 3
if t1.val != t2.val:
return False
# STEP 4, 10
return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
# STEP 1, 16
return isMirror(root.left, root.right) if root else True
📊
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.
✓ 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
Step 1: Trace heights and diameter updates for each node.
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.
Final Answer:
Option D -> Option D
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
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).
Step 2: Explain why complexity is linear
Because total edge traversals sum to O(n), the overall time complexity is O(n).
Final Answer:
Option D -> Option D
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
Step 1: Analyze order of operations
The code swaps children before recursively inverting subtrees, which means subtrees are swapped but not inverted themselves.
Step 2: Identify why swapping before recursion is incorrect
Swapping first causes recursion to invert the wrong subtrees, leading to partial or incorrect inversion.
Final Answer:
Option A -> Option A
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
Step 1: Understand traversal constraints
Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
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.
Final Answer:
Option D -> Option D
Quick Check:
Tracking previous node enables correct traversal without extra space [OK]
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
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.
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.
Step 3: Why other options fail
Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.
Final Answer:
Option A -> Option A
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 unknownstrongwhile earning +1 Grip toward your certificate.