On this page
Description
A tree is symmetric when its left half is a mirror image of its right half. Mirroring a tree swaps the children of every node. Both rest on one idea: pair nodes crossed, a left child with the other side's right child, instead of in parallel. Checking reads the pairs; mirroring writes them.
We'll go from simple to more technical:
- The pattern: a symmetry check comparing crossed pairs.
- A second flavor: producing the mirror by swapping at every node.
- Where mirrored structure matters in practice.
- The parallel-instead-of-crossed bug, and deep trees.
The approach: symmetry check (crossed comparison)
"Mirror" isn't the same as "identical". Hold a mirror to the left half, and its outer edge lines up with the right half's outer edge. So compare the root's two children. Then compare the outer pair: the left one's left child with the right one's right child. Then the inner pair: the left one's right child with the right one's left child. Repeat all the way down.
| Pair compared | Values | Next pairs |
|---|---|---|
| the root's children | 3 and 3: equal | the outer pair and the inner pair |
| outer: left's left, right's right | 1 and 1: equal | both missing children, so equal |
| inner: left's right, right's left | 4 and 4: equal | both missing children, so equal |
The tree is symmetric. Comparing in parallel instead, left's left with right's left, would pair 1 with 4 and wrongly say no.
Java
boolean isSymmetric(TreeNode root) {
return root == null || isMirror(root.left, root.right);
}
boolean isMirror(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return a.val == b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left);
}
Python
def is_symmetric(root: TreeNode | None) -> bool:
return root is None or is_mirror(root.left, root.right)
def is_mirror(a: TreeNode | None, b: TreeNode | None) -> bool:
if a is None and b is None:
return True
if a is None or b is None:
return False
return a.val == b.val and is_mirror(a.left, b.right) and is_mirror(a.right, b.left)
A second flavor: producing a mirror (crossed mutation)
To turn a tree into its mirror image, swap the two children of every node. Take a root 5 with children 3 and 8, where 3 has a left child 1. After mirroring, 5's children are 8 and 3, and 1 is now 3's right child.
Java
void mirrorTree(TreeNode root) {
if (root == null) return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorTree(root.left);
mirrorTree(root.right);
}
Python
def mirror_tree(root: TreeNode | None) -> None:
if root is None:
return
root.left, root.right = root.right, root.left # tuple assignment swaps without a temp
mirror_tree(root.left)
mirror_tree(root.right)
The check reads crossed pairs, and the mirror writes a crossed swap. It's the same idea used two ways.
Where you'll see it
Mirroring comes up when a layout must flip, such as turning a left-to-right UI tree into a right-to-left one for Arabic or Hebrew. It also helps normalize expression trees: for an operation like + where order doesn't matter, swapping operands into a fixed order lets equal expressions compare equal.
Which tool for which job?
| You need | Use |
|---|---|
| Is the tree symmetric? | compare (left, right) pairs crossed, recursively |
| The same on a very deep tree | a queue (or stack) of node pairs |
| Mirror the tree in place | swap children at every node |
| A mirrored copy, original untouched | build new nodes with crossed children |
| Are two trees mirrors of each other? | the symmetry check on (a, b) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Comparing a.left with b.left | checks "same tree", not "mirror" | a.left with b.right |
| Swapping only at the root | only the top level flips | swap at every node |
| Checking symmetry via an inorder palindrome | non-symmetric trees pass | compare the structure, crossed |
| Mirroring in place when the caller still needs the tree | the caller's tree changes | build a mirrored copy |
| Recursion on a very deep tree | stack overflow | a queue of pairs |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A check compares a.left with b.left and a.right with b.right. What does it really test?
Show answer
Whether the two subtrees are identical copies, not mirror images. That's the "same tree" check. The symmetric tree above fails it, because its halves are mirrored, not copied.
2. A mirror function recurses into the children before swapping them. Is that wrong?
Show answer
No. Each node's swap is independent of its children's swaps, so before or after makes no difference. What matters is that every node gets swapped. A node that's skipped leaves its subtree un-mirrored.
3. Is isSymmetric(root) the same as isSameTree(root.left, root.right)?
Show answer
No. One compares crossed pairs, the other parallel pairs. Most symmetric trees have halves that are mirror images but not identical, so they pass one check and fail the other.
Key takeaways
- Symmetry compares crossed pairs:
a.leftwithb.right. - Comparing in parallel tests for identical halves, a different property.
- A mirror image swaps the children of every node, not just the root.
- The check and the mirror are the same crossed pairing, once reading and once writing.