Symmetric Tree
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return True if the tree is a mirror image of itself — if you could fold it down a vertical line through the root and every node would land on a node with the same value.
Put another way, the left subtree must be the mirror of the right subtree. Two subtrees are mirrors when their roots have equal values, the first one’s left mirrors the second one’s right, and the first one’s right mirrors the second one’s left. Shape and values both count: the right values in the wrong places, or a child hanging on the wrong side, make it not symmetric.
Trees here are at most 500 levels deep, so a recursive solution is safe.
The node type and two helpers are provided:
Examples
Input: root = [1,2,2,3,4,4,3] Output: True
The left 2 has children 3, 4. Seen from the other side, the right 2 has children 4, 3 — exactly the reflection.
Input: root = [1,2,2,None,3,None,3] Output: False
Both 3s are right children. In a mirror, one of them would be a left child.
Constraints
- 1 <= number of nodes <= 1000
- -100 <= Node.val <= 100
- the tree is at most 500 levels deep (LeetCode allows 1,000; tightened so recursion fits in the browser)
Approaches
- Mirror a copy of one half, then compare — time O(n), space O(n)
Follow-up
Could you solve it both recursively and iteratively?
Related problems
Start free on Cariara · Coding problems · System design studio
