Problem overview
The function isSymmetric receives the root of a binary tree, a TreeNode?, and returns a Boolean: true if the tree is a mirror image of itself around its center line, false otherwise. Each node stores its number in value. The tree has between 1 and 1000 nodes, and values are between -100 and 100.
In the first example, the tree [1, 2, 2, 3, 4, 4, 3] in level order is symmetric. The root's left subtree has 3 and 4 below its 2, and the right subtree has 4 and 3 below its 2, which is the same picture reflected. In the second example, [1, 2, 2, null, 3, null, 3], both 2s have a child on the same side (the right) holding a 3. A mirror would need the children on opposite sides, so the answer is false.
Approach: compare two subtrees that should mirror each other
A tree is symmetric when its left subtree is the mirror image of its right subtree. To phrase that precisely, write a helper that asks whether two trees, root1 and root2, are mirrors of each other. They are, if and only if:
- both are empty, or
- both exist, their values are equal, and
- the left child of the first is a mirror of the right child of the second (the outer pair), and
- the right child of the first is a mirror of the left child of the second (the inner pair).
That definition is already a recursive algorithm. The top-level question, whether the whole tree is symmetric, is the helper's question about the root's two subtrees. The solution takes a shortcut: it passes the same root twice, dfs(root, root). The helper then walks two copies of one tree in opposite directions, left on one side while going right on the other. The first comparison, a node against itself, always succeeds, and the following ones compare the left subtree against the right one.
Take [1, 2, 2, null, 3, null, 3]. The helper starts with the root against itself, which is fine. Then it compares the outer pair: the left 2 against the right 2, with equal values. Next, the left child of the first 2 is absent, while the right child of the second 2 is the node 3. One side is empty and the other is not, so that call returns false, and so does the whole check.
Step by step
- Write
isSymmetricfirst. It returnsdfs(root, root), assuming the helper exists. - Declare the helper with two parameters,
root1androot2, bothTreeNode?, returningBoolean. - Both empty means a match. If
root1 == null && root2 == null, returntrue. This is the base case that ends the recursion at the bottom of the tree. - Exactly one empty means a mismatch. If either is
null, returnfalse. Because the previous check handled the case of both being null, only one can be missing here. The order of these two checks matters. - Different values mean a mismatch. Mirrored nodes must hold the same number.
- Check the outer pair. If
dfs(root1.left, root2.right)isfalse, returnfalseright away, and skip the other pair. - Return the inner pair. Its result,
dfs(root1.right, root2.left), is the answer for what is left.
The solution in Kotlin
class Solution {
fun 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)
}
fun isSymmetric(root: TreeNode?): Boolean {
return dfs(root, root)
}
}
The Kotlin details worth knowing:
- Smart casts after null checks. After the first two
ifstatements return, the compiler knows that neitherroot1norroot2isnull: if either were, the second check would have returned. Soroot1.valueandroot2.leftcompile without?.or!!. The smart cast works because both are parameters, which can't be reassigned. - Short-circuit operators.
&&and||stop as soon as the result is known. Inroot1 == null || root2 == nullthe second part is only evaluated when the first is false. ==on nullable values. In Kotlin==is safe againstnull:root1 == nullis just a check, and it never throws. It also callsequalsfor other objects, which is why comparing the integer fields with!=compares their values.- Early returns. The function is a series of guard clauses: each
ifsettles one case and returns, and the last line carries the final answer. The negation!dfs(...)flips theBooleanresult.
Complexity
Let n be the number of nodes and h the height of the tree.
Time: O(n). Each call compares one position on the left side with its mirror on the right and then makes at most two more calls. Because the root is passed twice, every node is visited twice, once from each side, so the work is a constant multiple of n. A mismatch stops the process early.
Space: O(h). Only the recursion uses memory, one frame per level of depth. That is about log n for a balanced tree and up to n for a chain, though with at most 1000 nodes even a chain is safe.
Edge cases and common mistakes
- Single node.
[1]is symmetric. Both children of the root are absent, so both calls returntrue. - Same shape, different values.
[1, 2, 3]has a mirrored shape but the values 2 and 3 differ, so the answer isfalse. - Same values, wrong shape.
[1, 2, 2, null, 3, null, 3]has matching values but the 3s hang on the same side, so the answer isfalse. - Comparing left with left. Pairing
root1.leftwithroot2.left, and right with right, checks that two trees are identical, not mirrored. Sincedfs(root, root)passes the same tree twice, such a check would always returntrue, even for[1, 2, 3]. - Swapping the two null checks. If the "either is null" check came first, two empty subtrees would be reported as a mismatch, and every tree would be rejected at its leaves.
- Checking only the values. Equal values on both sides are not enough. The positions must be reflected, which is why the outer and inner pairs are crossed.
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.