Problem overview
The function is_symmetric receives the root of a binary tree, as an Option<Box<TreeNode>>, and returns true when the tree is a mirror image of itself around its center. The tree has between 1 and 1,000 nodes and values from -100 to 100.
The tree [1, 2, 2, 3, 4, 4, 3] is symmetric: the left subtree (2 with children 3 and 4) is the mirror of the right subtree (2 with children 4 and 3). The tree [1, 2, 2, null, 3, null, 3] is not. Both 2s have a single child 3, but on the same side, so the shapes are not mirrored.
Approach: compare two subtrees that should be mirrors
Asking whether a whole tree is symmetric is the same as asking whether its left and right subtrees mirror each other. So the real task is a function that takes two subtrees, left and right, and decides whether one is the mirror of the other. Two subtrees mirror each other when:
- both are empty; or
- both exist, their root values are equal, and the outer pair mirrors (the left child of the first against the right child of the second) and the inner pair mirrors (the right child of the first against the left child of the second).
If exactly one of them is empty, they cannot mirror each other.
Comparing "left with left" would test whether two subtrees are identical, which is a different question. A mirror flips the sides, which is why the outer and inner pairs cross over.
The check visits each node once, so it is much cheaper than building a mirrored copy of the tree and comparing it afterwards.
Step by step
- Decide the entry point. In
is_symmetric, match onroot. An empty tree (None) is symmetric, so that arm givestrue. Otherwise bind the root asnodeand returnSelf::dfs(node.left, node.right). The root is passed by value and moved, so it can't be given to the helper twice. Comparing its two children covers the same ground. - Declare
dfswith two parameters,leftandright, bothOption<Box<TreeNode>>, returningbool. Its body is onematchon the pair(left, right), so both values are inspected together. - Two empty subtrees: the arm
(None, None) => true. - Two present nodes: an arm
(Some(l), Some(r))with a block body, binding the boxed nodes aslandr. - Compare the values: if
l.val != r.val,return falseat once. - Cross-compare the children: end the arm with
Self::dfs(l.left, r.right) && Self::dfs(l.right, r.left), without a semicolon, so it is the arm's value. - Everything else: the last arm
_ => falsecovers the case where exactly one side is empty. Rust requires amatchto be exhaustive, and this arm completes it.
The solution in Rust
impl Solution {
fn dfs(left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>>) -> bool {
match (left, right) {
(None, None) => true,
(Some(l), Some(r)) => {
if l.val != r.val {
return false;
}
Self::dfs(l.left, r.right) && Self::dfs(l.right, r.left)
}
_ => false,
}
}
fn is_symmetric(root: Option<Box<TreeNode>>) -> bool {
match root {
None => true,
Some(node) => Self::dfs(node.left, node.right),
}
}
}
Rust details that matter here:
- Matching on a tuple.
match (left, right)builds a tuple that owns both options and then matches the pair in one go. The arm patterns,(None, None),(Some(l), Some(r))and_, between them cover all four combinations of present and missing. - Moving out of boxes. In the second arm,
landrareBox<TreeNode>values. Their fields can be moved out one by one:l.leftandr.rightgo into one recursive call, andl.rightandr.leftinto the other. The tree is consumed as it is checked, which is fine because the function owns it.l.valandr.valareCopyintegers, and they are read before any field is moved. - Short-circuit
&&. The second recursive call is evaluated only if the first returnedtrue. A mismatch on the outer pair stops the whole check early. - Early
return. Thereturn falseinside the arm leaves the function immediately. The final expression has no semicolon, so it is the value of the arm, and so of the wholematch, and of the function. - Why the helper isn't called with the root twice. An
Option<Box<TreeNode>>is moved when it is passed by value, soSelf::dfs(root, root)would not compile. Passing the root's two children works, and it checks the same condition.
Complexity
Time: O(n). Each node is paired with exactly one other node, so every node is looked at once, and the recursion ends at the first mismatch if there is one.
Space: O(h). The recursion is as deep as the tree is tall, h. That is about log n for a balanced tree and up to n for a tree shaped like a chain.
Edge cases and common mistakes
- Single node.
[1]is symmetric. Both children areNone, sodfsreturnstrue. - Same values, different shape.
[1, 2, 2, null, 3, null, 3]returnsfalse. The left 2 has a right child, the right 2 has a right child as well, and the cross comparison pairs a present node with a missing one. - Same shape, different values.
[1, 2, 3]returnsfalsebecause 2 and 3 differ.[1, 2, 2, 3, 4, 5, 3]returnsfalsebecause the inner pair 4 and 5 differs. - One-sided tree.
[1, 2]returnsfalse: the left child exists and the right one doesn't, which hits the_ => falsearm. - Comparing the wrong pairs. Using
dfs(l.left, r.left)anddfs(l.right, r.right)checks for identical subtrees. For[1, 2, 2, 3, null, 3, null]that would answertrue, but the correct answer isfalse, because a mirror image of a left child must be a right child. - Forgetting the value check. Without it, a tree such as
[1, 2, 3]would pass as symmetric, since the structure matches.
Testing
[1, 2, 2, 3, 4, 4, 3]givestrue.[1, 2, 2, null, 3, null, 3]givesfalse.[1, 2, 2, 3, null, null, 3]givestrue.[1]givestrue.[1, 2]givesfalse.
