Problem overview
The method isSymmetric receives the root of a binary tree as a TreeNode? and returns true when the tree is a mirror image of itself around its center, and false otherwise. Both shape and values count: the left half must be the right half flipped.
The tree [1, 2, 2, 3, 4, 4, 3] is symmetric. The root's two children are both 2. The left 2 has children 3 and 4, the right 2 has children 4 and 3, so the outer pair (3 and 3) and the inner pair (4 and 4) match. The tree [1, 2, 2, null, 3, null, 3] is not symmetric: both 2s have only a right child, 3. The left 2's right child would have to pair with the right 2's left child, and that child is missing. The shapes differ, so the answer is false.
Approach: compare two nodes that should mirror each other
Comparing the left subtree with the right subtree directly isn't enough, because a mirror reverses the sides. A node's left child must match the other node's right child. So the helper takes two nodes and asks whether the subtrees under them are mirror images of each other. Two subtrees mirror each other when:
- both are empty; or
- both exist, hold the same value, the first one's left subtree mirrors the second one's right subtree, and the first one's right subtree mirrors the second one's left subtree.
To check a whole tree, compare it with itself. The helper is called as dfs(root, root): one copy is followed on the left side while the other is followed on the right side. At the top, the two nodes are the same root, which trivially matches itself. The check then goes to the pair (left child, right child) and so on down.
The same idea, applied to [1, 2, 2, 3, 4, 4, 3]: at the root, the two nodes are both 1. Their values match. The outer pair is the root's left child compared with its right child, 2 and 2, which match. Under them, the left 2's left child (3) is compared with the right 2's right child (3), and the inner pair (4 and 4) comes next. Every pair matches, so the result is true.
Step by step
- Return
dfs(root, root)fromisSymmetric. The helper does the real work, and a tree is symmetric when it mirrors itself. - Declare the helper
dfsabove it, with two unlabeled parameters_ root1and_ root2, bothTreeNode?, returningBool. - Both empty: return
true. Two empty subtrees mirror each other. This is the base case that ends the recursion at the leaves. - Exactly one empty: return
false. The previous check already handled the case of both being empty, so this condition only fires when exactly one of them is. - Different values: return
false. Both nodes exist here, so!is safe. - Check the outer pair. Compare
root1!.leftwithroot2!.right. If that call returnsfalse, returnfalseimmediately. - Return the inner pair's result:
dfs(root1!.right, root2!.left)is the last thing to check, so its answer is the answer.
The solution in Swift
class Solution {
func dfs(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
if root1 == nil && root2 == nil {
return true
}
if root1 == nil || root2 == nil {
return false
}
if root1!.val != root2!.val {
return false
}
if !dfs(root1!.left, root2!.right) {
return false
}
return dfs(root1!.right, root2!.left)
}
func isSymmetric(_ root: TreeNode?) -> Bool {
return dfs(root, root)
}
}
Swift details worth a closer look:
- Optional parameters. Both parameters are
TreeNode?, so a missing child can be passed straight in asnilwithout a separate check by the caller. - Order of the
nilchecks. The conditionroot1 == nil || root2 == nilsays "at least one", and it only means "exactly one" because the "both" case already returned. Moving it above the first check would send a pair of empty subtrees tofalse. - Force-unwrapping. After the two checks, neither node is
nil, soroot1!.valandroot2!.valare safe. In other code,guard letwould avoid!. - Unlabeled parameters. The underscores let the calls read
dfs(root, root)with no argument labels. - Short-circuit by
return. The outer pair is checked in its ownif. If it fails, the function returns before evaluating the inner pair. The final line returns the inner pair'sBooldirectly, so noifis needed for it.
Complexity
Let n be the number of nodes and h the height.
Time: O(n). Each call compares one pair of positions, and each node is visited at most twice, once as the first argument and once as the second, because the whole tree is compared with itself. The calls on missing children add at most a constant factor. Each call does constant work, and the search stops early at the first mismatch.
Space: O(h). The only extra memory is the recursion, which goes as deep as the tree. That is about log n for a balanced tree and n for a chain.
Edge cases and common mistakes
- A single node.
[1]is symmetric: the pair at the root is the node with itself, and all children are empty. - A root with one child.
[1, 2]is not symmetric. The outer pair has the node 2 on one side andnilon the other. - Same shape, different values.
[1, 2, 3]has a symmetric shape but not symmetric values: 2 against 3 fails the value check. - Same values, wrong shape.
[1, 2, 2, 3, null, null, 3]is symmetric, but[1, 2, 2, null, 3, null, 3]is not: the second has the same values, but the 3s sit on the same side of each 2 instead of on opposite sides. - Comparing the wrong children. Pairing
root1!.leftwithroot2!.leftchecks whether two trees are identical, not whether they mirror each other. - An empty tree. The constraints promise at least one node, but
nilwould also work:dfs(nil, nil)returnstrue.
Testing
[1, 2, 2, 3, 4, 4, 3]givestrue.[1, 2, 2, null, 3, null, 3]givesfalse.[1]givestrue.[1, 2]givesfalse.[1, 2, 3]givesfalse.[1, 2, 2, 3, null, null, 3]givestrue.
