Problem overview
The method isSymmetric receives the root of a binary tree and returns true when the tree is a mirror image of itself around its center. The shape and the values must both match.
The tree with root 1, children 2 and 2, and grandchildren 3, 4 under the left 2 and 4, 3 under the right 2 is symmetric: the right half is the left half reflected, with 3 and 4 swapped in position. The tree with root 1 and two children 2 whose only children are a right child 3 on each side is not symmetric. A mirror would need the left 2 to have its child on the left, because the right 2 has it on the right.
Approach: compare two subtrees at once
Two trees are mirrors of each other when their roots hold equal values, the left subtree of the first mirrors the right subtree of the second, and the right subtree of the first mirrors the left subtree of the second. That rule is recursive, and it also defines symmetry: a tree is symmetric when it mirrors itself.
So the helper dfs(root1, root2) takes two nodes that should be mirror images. It looks at a pair, and then it recurses into two more pairs: the outer pair, which is root1.left with root2.right, and the inner pair, which is root1.right with root2.left. The main method starts with the tree and a second walk through the same tree: dfs(root, root). Walking the same tree twice works because the two walks go in opposite directions, left on one side while right on the other.
Step by step
- Start the check by returning
dfs(root, root)fromisSymmetric. - Declare the helper above it, with two
TreeNodeparameters,root1androot2, and the result typeBoolean. - Both empty. If
root1 == null && root2 == null, returntrue. Two empty subtrees mirror each other. This is the base case for the leaves. - Exactly one empty. If
root1 == null || root2 == null, returnfalse. The previous check removed the case of both being empty, so here only one of them is, and the shapes differ. The order of these two checks matters. - Different values. If
root1.value != root2.value, returnfalse. Both nodes exist at this point, so reading their values is safe. - Outer pair. If
dfs(root1.left, root2.right)is false, returnfalseat once. The inner pair no longer matters. - Inner pair. Return
dfs(root1.right, root2.left). If the outer pair matched, this call decides the answer.
The solution in Scala
class Solution {
def dfs(root1: TreeNode, root2: TreeNode): Boolean = {
if (root1 == null && root2 == null) {
return true
}
if (root1 == null || root2 == null) {
return false
}
if (root1.value != root2.value) {
return false
}
if (!dfs(root1.left, root2.right)) {
return false
}
return dfs(root1.right, root2.left)
}
def isSymmetric(root: TreeNode): Boolean = {
return dfs(root, root)
}
}
Scala details:
nulland==. In Scala,==on references is a null-safe value comparison, soroot1 == nullis fine even whenroot1is null. Readingroot1.valueon a null, by contrast, throws aNullPointerException, which is why thenullchecks come first.&&and||short-circuit. The right-hand operand is evaluated only when it is needed. Inroot1 == null || root2 == null, the second test runs only when the first is false.returnis optional on the last line of a method. The early returns inside theifblocks are needed, as they leave the method before the later lines. They are at the method's own level and not inside a closure, so they behave as in any language.- A
Booleanmethod. A method with a declared result typeBooleanmust give aBooleanon every path. Here every branch returns one. - Negation.
!dfs(...)negates the call's result.
Complexity
Time: O(n). Each call compares one pair of positions and does constant work. A node can be the first argument of at most one call and the second argument of at most one call, since the two walks descend together, so the number of calls is at most about 2n plus the calls on missing children. A mismatch ends the work early.
Space: O(h), where h is the height of the tree, for the recursion. A chain of nodes is a worst case, and a perfectly balanced tree has about log n levels. With the lesson's limit of 1,000 nodes the recursion is never a problem.
Edge cases and common mistakes
- A single node is symmetric:
dfs(root, root)compares the node with itself and then two empty pairs. - A node with one child is not symmetric: the root 1 with only a left child 2 compares that child with a missing right child and fails the one-sided check.
- Different values. A tree with root 1 and children 2 and 3 fails on the values of the first pair.
- Same values in the wrong place. Comparing
root1.leftwithroot2.leftinstead ofroot2.rightwould test whether two trees are identical, not mirrored. The outer and inner pairs are the heart of the solution. - Checking the values of only the first level. A symmetric-looking top can hide a different shape lower down, as in the second example above, where the 3s are on the same side.
- Swapping the two
nullchecks. If the "one is null" test came first, two empty subtrees would be reported as different.
Testing
- Root 1 with children 2, 2 and grandchildren 3, 4 / 4, 3:
true. - Root 1 with children 2, 2 that each have only a right child 3:
false. - A single node:
true. - Root 1 with children 2 and 3:
false. - Root 1 with one child:
false.
