JuniorCodeVery commonNot answered yet
Check whether a binary tree is symmetric
Given the root of a binary tree, return whether it is a mirror image of itself (symmetric around its centre).
Requirements:
- Compare the left and right subtrees as mirrors; an empty tree is symmetric.
struct Node { Node* l; Node* r; int value; };
bool isSymmetric(Node* root) {
// your code here
}Write the implementation.
Symmetry is a mirror property of the two subtrees, not of a single node. Recurse comparing left against right: two nodes mirror iff their values match and left.l mirrors right.r and left.r mirrors right.l. Both null is symmetric; one null is not. An empty tree is symmetric. O(n) time.
- ✗Comparing a node's own two children instead of mirroring across the two subtrees
- ✗Treating one-null/one-present as a match instead of a failure
- ✗Relying on a traversal-palindrome, which passes for non-symmetric trees
- →Why is comparing a node's own left and right children insufficient?
- →How would you write this iteratively with a queue?
Contents
Task
Check whether a binary tree is symmetric about its centre. In O(n).
Solution
struct Node { Node* l; Node* r; int value; };
static bool mirror(Node* a, Node* b) {
if (!a && !b) return true; // both empty — mirrored
if (!a || !b) return false; // only one empty — not
return a->value == b->value
&& mirror(a->l, b->r) // outer sides
&& mirror(a->r, b->l); // inner sides
}
bool isSymmetric(Node* root) {
return root == nullptr || mirror(root->l, root->r);
}Key points
- Mirror across the subtrees:
a->lwithb->r,a->rwithb->l. - Comparing a single node's own children is not enough for global symmetry.
- An empty tree and a null pair count as symmetric; one null is a failure.
Contents
