Given the root of a binary tree, check whether it is a mirror of itself. In other words, the left subtree must be a mirror image of the right subtree.
DSA Animator › DSA Revision › Tree › Symmetric Tree
Remember: compare outside with outside, and inside with inside. Pass two nodes into the recursion, not one. The video solves Symmetric Tree (LeetCode 101, Easy) with the Mirror Recursion pattern from the Tree topic, and you can replay every step in the interactive Symmetric Tree animation.
Given the root of a binary tree, check whether it is a mirror of itself. In other words, the left subtree must be a mirror image of the right subtree.
The tree 1, with children 2 and 2, and grandchildren 3, 4, 4, 3, is symmetric. If the grandchildren were missing, 3, missing, 3, it would not be symmetric.
You could collect each level and check whether it reads the same both ways. But you must also record missing children, which makes it messy. A recursive mirror check is simpler.
Write a helper that compares two nodes, a and b, that should mirror each other. If both are null, they match. If only one is null, or their values differ, they do not match. Otherwise, the outside pair must match, which is a left with b right. And the inside pair must match, which is a right with b left.
Start by comparing the two 2s, the root children. Their values are equal, so check the outside pair: 3 on the far left against 3 on the far right. Both 3s match, and their children are all null, so that pair is fine. Now check the inside pair: 4 against 4. They also match, with null children. Every pair matched, so the tree is symmetric.
In code, return mirror of root left and root right. In mirror, return true if both are null, and false if only one is null. Otherwise return whether the values are equal, the outside pair mirrors, and the inside pair mirrors. Each node is compared once, so it's O of n time and O of the height in stack space.
Remember: compare outside with outside, and inside with inside. Pass two nodes into the recursion, not one.