Symmetric Binary Tree
MediumCompare left against right, mirrored
Problem
Return whether a binary tree is a mirror image of itself.
Compare the left subtree against a mirror of the right subtree, node by node.
The idea
A tree is symmetric when its left subtree mirrors its right, which means comparing left.left with right.right and left.right with right.left. Pairing the outer and inner children crosswise is the entire idea.
The trick
- Compare outer with outer and inner with inner, not left with left.
- Both null is symmetric; one null is not.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,2,3,4,4,3] Values: 1, 2, 2, 3, 4, 4, 3.
1mirror(a,b):2 if a==null and b==null: true3 if a==null or b==null or a.val!=b.val: false4 return mirror(a.left,b.right) and mirror(a.right,b.left)Input
- array
- [1, 2, 2, 3, 4, 4, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,2,3,4,4,3]
- Output:
- true
- Explanation:
- The tree mirrors itself down the middle.
Example 2
- Input:
- tree = [1,2,2,null,3,null,3]
- Output:
- false
- Explanation:
- The right/left don't mirror → false.
Example 3
- Input:
- tree = [1]
- Output:
- true
- Explanation:
- A single node is symmetric.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.