How do you approach Symmetric Tree?

Build the tree from the array, then check if the left subtree is a mirror of the right subtree.

What is the time complexity of Symmetric Tree?

Time complexity: O(n) - visit each node once. Space complexity: O(n) - recursion stack in worst case.

What are common mistakes on Symmetric Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Symmetric Tree

EasyData Structures

Description

Given the root of a binary tree represented as a level-order array (with `null` for missing nodes), check whether it is a mirror of itself (i.e., symmetric around its center). For example, `[1, 2, 2, 3, 4, 4, 3]` represents: ``` 1 / \ 2 2 / \ / \ 3 4 4 3 ``` This tree is symmetric. But `[1, 2, 2, null, 3, null, 3]` is not: ``` 1 / \ 2 2 \ \ 3 3 ```

Example 1

Input: root = [1, 2, 2, 3, 4, 4, 3]

Output: true

Example 2

Input: root = [1, 2, 2, null, 3, null, 3]

Output: false

Constraints

- The number of nodes in the tree is in the range [1, 1000]. - -100 <= Node.val <= 100

Symmetric Tree: approach, complexity and pitfalls

An easy trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Build the tree from the array, then check if the left subtree is a mirror of the right subtree.
Two trees are mirrors if their roots have the same value and the left subtree of one is a mirror of the right subtree of the other.
You can also solve this iteratively using a queue.

The optimal approach

Show the approach: Recursive Mirror Check

Build the tree from the level-order array. Then recursively check if the tree is symmetric by comparing the left and right subtrees as mirrors.

Two subtrees are mirrors if:

1. Both are null, or

2. Both have the same value, and the left child of one mirrors the right child of the other.

Time: O(n) - visit each node once
Space: O(n) - recursion stack in worst case

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.