Skip to main content

101. Symmetric Tree

easy

Determine whether a binary tree is a mirror image of itself around its center. Tests two-tree recursion under a structural-mirror predicate.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Compare left subtree with right subtree treated as a 'mirror'.

Hint 2

Helper isMirror(a, b): both null = true; one null = false; values differ = false.

Hint 3

Then isMirror(a.left, b.right) AND isMirror(a.right, b.left) — note the CROSS pairing.

Solution approach

Reveal approach

Two-tree recursion with cross-pairing. Helper isMirror(a, b): if both null, return true; if exactly one is null, return false; if a.val != b.val, return false. Otherwise return isMirror(a.left, b.right) AND isMirror(a.right, b.left) — the crucial detail is the cross: a's left mirrors b's right and vice versa. Top-level call: isMirror(root.left, root.right) (or true if root is null). O(n) time, O(h) recursion space. Iterative variant: BFS queue with pairs (a, b) processed in mirror order.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dfs
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

More Trees practice problems

See all Trees problems →