Problem overview
The method isSymmetric receives the root of a binary tree, a TreeNode | null, and returns a boolean: true when the tree is a mirror image of itself around its centre, and false otherwise. The tree has between 1 and 1000 nodes, with values from -100 to 100.
The tree built from [1,2,2,3,4,4,3] is symmetric. Under the root 1, both children hold 2. The left 2 has children 3 and 4, and the right 2 has children 4 and 3, which is the left side read backwards. The answer is true.
The tree built from [1,2,2,null,3,null,3] is not. Both 2s have only one child, and that child is a 3 hanging on the right of each. The mirror image of a right child would be a left child, so the answer is false.
Approach: compare two subtrees that should mirror each other
Two trees are mirror images of each other when:
- their roots hold the same value;
- the left subtree of the first mirrors the right subtree of the second;
- the right subtree of the first mirrors the left subtree of the second.
That is a recursive definition, so a helper dfs(root1, root2) can check it. The tree is symmetric when its left half mirrors its right half. A neat way to start is to pass the same tree as both arguments: dfs(root, root). The two parameters then walk the same tree in opposite directions, one moving left while the other moves right.
The helper has three base cases, in this order:
- Both nodes are missing: two empty subtrees mirror each other, so return
true. - Exactly one node is missing: the shapes differ, so return
false. - Both exist but hold different values: return
false.
If none of these fires, the nodes match, and the answer depends on the children: the outer pair (left of the first, right of the second) and the inner pair (right of the first, left of the second) must both mirror.
A common alternative is to build a mirrored copy of the tree and compare it with the original. That needs extra memory and an extra pass. Comparing in place is simpler.
Step by step
- Call the helper with the same tree twice, and return its answer from
isSymmetric. - Declare the helper with two parameters, both
TreeNode | null, returningboolean. - Handle two missing nodes by returning
true. This is the base case that ends the recursion at the leaves. - Handle exactly one missing node by returning
false. The order matters: this check is correct only because the both-missing case has already returned. - Compare the values. If they differ, return
false. Both nodes exist now, so readingvalis safe. - Check the outer pair: the first node's left child against the second node's right child. If they don't mirror, return
falseright away. - Return the result for the inner pair: the first node's right child against the second node's left child. Nothing else remains to check, so this call's result is the answer.
The solution in TypeScript
class Solution {
dfs(root1: TreeNode | null, root2: TreeNode | null): boolean {
if (!root1 && !root2) {
return true;
}
if (!root1 || !root2) {
return false;
}
if (root1.val != root2.val) {
return false;
}
if (!this.dfs(root1.left, root2.right)) {
return false;
}
return this.dfs(root1.right, root2.left);
}
isSymmetric(root: TreeNode | null): boolean {
return this.dfs(root, root);
}
}
The TypeScript details worth a closer look:
- Narrowing across checks. After the second
ifreturns, the compiler knows that bothroot1androot2are real nodes, soroot1.valandroot1.leftare accepted. !nodeon objects. A node is an object, which is always truthy, andnullis falsy. So!root1is true exactly whenroot1isnull.!=versus!==. The reference uses the loose!=. For two numbers it behaves the same as!==. The strict form is the safer habit, because loose comparison converts types when they differ.- Same tree, two parameters. Passing
roottwice doesn't copy anything. Both parameters refer to the same object, and the helper only reads from them. - Short-circuiting by returning. The early
return falseafter the outer pair skips the inner pair when the outer pair already fails.
Complexity
Let n be the number of nodes and h the height.
Time: O(n). Each node is visited at most twice, once from each side of the comparison, and each visit does a constant amount of work. The search ends early at the first mismatch.
Space: O(h). Only the recursion uses memory, one call per level of the tree. It is O(log n) for a balanced tree and O(n) for a chain.
Edge cases and common mistakes
- A single node.
[1]is symmetric. Both pairs of children are missing, so both calls returntrue. - A root with only one child.
[1,2]is not symmetric: one side is missing, so the second base case returnsfalse. - Same shape, different values.
[1,2,3]has a symmetric shape but is not symmetric, because 2 and 3 differ. - Mirrored shape with equal values.
[1,2,2,3,null,null,3]is symmetric: the left 2 has a left child, the right 2 has a right child. - Comparing the wrong pairs. Pairing left with left and right with right checks whether two trees are identical, not mirrored. The pairs must be crossed.
- Swapping the base cases. If the one-missing check came first, two missing nodes would be reported as a mismatch. The both-missing case must come first.
- Comparing only values level by level. Equal values are not enough: the shape must mirror too, so a node missing on one side must also be missing on the other.
Testing
[1,2,2,3,4,4,3]givestrue.[1,2,2,null,3,null,3]givesfalse.[1]givestrue.[1,2,3]givesfalse.[1,2,2,3,null,null,3]givestrue.