Symmetric Tree — Solution in Python, Java & C++
Symmetric Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Symmetric Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft, Bloomberg and LinkedIn interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Bloomberg, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return true if the tree is a mirror image of itself around its centre line — its left subtree is the reflection of its right subtree, in shape and in values — and false otherwise.
Example 1
Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: Reflecting the left subtree `2 → (3, 4)` gives `2 → (4, 3)`, which is exactly the right subtree.
Example 2
Input: root = [1,2,2,null,3,null,3]
Output: false
Explanation: Both 3s are right children; a mirror image would need one of them on the left.
Example 3
Input: root = [7]
Output: true
Constraints
The number of nodes in the tree is in the range [1, 1000]-100 <= Node.val <= 100
Follow-up: Can you solve it both recursively and iteratively?
Hints for Symmetric Tree
Hint 1
Symmetry is a relation between two subtrees: the root's left and right.
Hint 2
Two trees
aandbare mirrors when their roots match,a.leftmirrorsb.right, anda.rightmirrorsb.left.Hint 3
Iteratively, put pairs
(a, b)on a queue and push(a.left, b.right)and(a.right, b.left)for each matching pair.
How to solve Symmetric Tree
A tree is symmetric when its left subtree is the mirror of its right subtree. Check that with a helper mirror(a, b) that walks the two subtrees in opposite directions at the same time.
Approach
- Return
mirror(root.left, root.right). mirror(a, b): if both are null returntrue; if exactly one is null returnfalse.- If
a.val != b.valreturnfalse. - Return
mirror(a.left, b.right) && mirror(a.right, b.left).
Why it works
Reflecting a tree swaps left and right at every level, so the node at the position reached by a path of left/right turns on one side must equal the node reached by the opposite turns on the other. The helper compares exactly those position pairs, outer with outer and inner with inner.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth (a queue of pairs uses O(width) instead)
Pitfalls
- Comparing
a.leftwithb.leftchecks equality, not reflection. - Equal level-order value lists are not enough when nulls are ignored — positions matter.
Reference solution
Python
from typing import Optional
def isSymmetric(root: Optional[TreeNode]) -> bool:
def mirror(a, b):
if a is None or b is None:
return a is b
return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
return root is None or mirror(root.left, root.right)Java
public static boolean isSymmetric(TreeNode root) {
return root == null || mirror(root.left, root.right);
}
static boolean mirror(TreeNode a, TreeNode b) {
if (a == null || b == null) return a == b;
return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}C++
bool mirrorPair(TreeNode* a, TreeNode* b) {
if (!a || !b) return a == b;
return a->val == b->val && mirrorPair(a->left, b->right) && mirrorPair(a->right, b->left);
}
bool isSymmetric(TreeNode* root) {
return !root || mirrorPair(root->left, root->right);
}JavaScript
var isSymmetric = function(root) {
return root === null || mirror(root.left, root.right);
};
var mirror = function(a, b) {
if (a === null || b === null) return a === b;
return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)