Symmetric Tree
Check whether a binary tree is a mirror of itself by comparing left/right subtrees pairwise.
3 min read
tree bfs recursion
Problem#
Determine whether a binary tree is symmetric around its center — i.e., the left subtree is a mirror of the right subtree.
Examples#
[1,2,2,3,4,4,3]→true.[1,2,2,null,3,null,3]→false.
Constraints#
1 <= n <= 1000,-100 <= Node.val <= 100.
Hints#
Hint
Walk both halves in lockstep — compare left.left with right.right and left.right with right.left.
Approach#
A recursive helper mirror(a, b) returns true iff a and b have equal values and their cross-paired children mirror each other. The BFS version pushes both subtrees into a queue and pops two at a time.
Solution#
class Solution {public: bool isSymmetric(TreeNode* root) { if (!root) return true; function<bool(TreeNode*, TreeNode*)> mirror = [&](TreeNode* a, TreeNode* b) { if (!a && !b) return true; if (!a || !b) return false; if (a->val != b->val) return false; return mirror(a->left, b->right) && mirror(a->right, b->left); }; return mirror(root->left, root->right); }};func isSymmetric(root *TreeNode) bool { if root == nil { return true } var mirror func(a, b *TreeNode) bool mirror = func(a, b *TreeNode) bool { if a == nil && b == nil { return true } if a == nil || b == nil { return false } if a.Val != b.Val { return false } return mirror(a.Left, b.Right) && mirror(a.Right, b.Left) } return mirror(root.Left, root.Right)}from typing import Optional
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True
def mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool: if not a and not b: return True if not a or not b: return False if a.val != b.val: return False return mirror(a.left, b.right) and mirror(a.right, b.left)
return mirror(root.left, root.right)var isSymmetric = function(root) { if (!root) return true; const mirror = (a, b) => { if (!a && !b) return true; if (!a || !b) return false; if (a.val !== b.val) return false; return mirror(a.left, b.right) && mirror(a.right, b.left); }; return mirror(root.left, root.right);};class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) return true; return mirror(root.left, root.right); }
private boolean mirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null) return false; if (a.val != b.val) return false; return mirror(a.left, b.right) && mirror(a.right, b.left); }}function isSymmetric(root: TreeNode | null): boolean { if (!root) return true; const mirror = (a: TreeNode | null, b: TreeNode | null): boolean => { if (!a && !b) return true; if (!a || !b) return false; if (a.val !== b.val) return false; return mirror(a.left, b.right) && mirror(a.right, b.left); }; return mirror(root.left, root.right);}Editorial#
Mirror equality differs from regular tree equality: the recursive descent crosses the diagonal. Both null is symmetric; exactly one null is not. The check generalizes to BFS by enqueuing pairs.
Complexity#
- Time: O(n).
- Space: O(h) recursion stack, worst-case
O(n).
Concept revision#
Related#