1. Symmetric Tree (LeetCode)
Model answer
The task
Determine whether a binary tree is symmetric around its center: its left and right subtrees must be mirror images.
Key idea
Compare nodes in mirrored pairs. For each pair, their values must match, and their outer children and inner children must also match as mirrored pairs.
Approach
- Put the root’s left and right children into a queue as a pair.
- Remove a pair; if both nodes are absent, continue. If only one is absent or their values differ, return
False. - Add the outer pair of children and the inner pair of children to the queue.
- If every pair matches, return
True.
from collections import deque
from typing import Optional
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
queue = deque([(root.left, root.right)])
while queue:
left, right = queue.popleft()
# Missing nodes must occur in matching positions.
if left is None or right is None:
if left is not right:
return False
continue
if left.val != right.val:
return False
# Compare mirrored child positions.
queue.append((left.left, right.right))
queue.append((left.right, right.left))
return True
Complexity:
- Time: O(n), where n is the number of nodes; each node is checked at most once.
- Space: O(n) in the worst case for the queue.
Common follow-ups
- Can this be solved recursively? Yes; define a helper that checks a pair of mirrored nodes and recursively compares their outer and inner children.
- What if node values are not unique? The method still works because it checks both values and structure.
- What if the tree is very deep? The iterative queue avoids recursion-depth limits; its memory use depends on the tree’s maximum width.