Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself, that is, symmetric around its centre.
Constraints:
- The number of nodes is in the range
[1, 1000]. -100 <= Node.val <= 100
Intuition
1 12 / \3 2 24 / \ / \5 3 4 4 3This tree is symmetric. The left subtree is the mirror image of the right subtree.
Two trees are mirrors of each other if their roots have the same value, and the left child of one mirrors the right child of the other, and the right child of one mirrors the left child of the other. Compare with Same Tree: it is the same recursion with the children crossed.
Approach: Compare Two Subtrees as Mirrors
- If the root is
null, the tree is symmetric. - Otherwise call
isMirror(root.left, root.right). - In
isMirror(a, b):- If either is
null, returna == b(true only if both are null). - If
a.val != b.val, return false. - Return
isMirror(a.left, b.right) && isMirror(a.right, b.left).
- If either is
The crossing of left with right is the only thing that makes this a mirror check rather than an equality check.
Code
class Solution {bool isMirror(TreeNode* a, TreeNode* b) {if (a == nullptr || b == nullptr) return a == b;if (a->val != b->val) return false;return isMirror(a->left, b->right) && isMirror(a->right, b->left);}public:bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;return isMirror(root->left, root->right);}};
Complexity
Time: O(n)
Each node is compared once, in a pair with its mirror node.
Space: O(h)
Recursion stack depth equals the tree height.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"A tree is symmetric if its left subtree is a mirror of its right subtree. Two trees are mirrors if their roots have the same value, the left of the first mirrors the right of the second, and the right of the first mirrors the left of the second. So I write a helper that takes two nodes. If either is null I return whether both are null. If the values differ I return false. Otherwise I recurse on the crossed pairs and combine with AND. It is the same tree check, just with left and right crossed. Time is O of n and space is O of h."
Next TopicRoot to Node Path in Binary Tree