Command Palette

Search for a command to run...

Hectal
Problem 16.4 · Binary TreesEasy

Symmetric Tree

PatternTree DFS

What it teaches: Compare a tree with its own mirror: outer children with outer, inner with inner.

Practise it on judges as “Symmetric Tree”.

The problem

Return true if a binary tree is a mirror image of itself around its centre.

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

  • 1 ≤ nodes ≤ 1000

Pattern clues in the wording

  • → Mirror comparison of two subtrees

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [1,2,2,3,4,4,3]
true
2
root = [1,2,2,null,3,null,3]
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive mirror check · O(n)
1

Recursive mirror check

Time O(n) Space O(h)

isMirror(a, b): both null → true; one null or values differ → false; else isMirror(a.left, b.right) && isMirror(a.right, b.left).

Approach 1
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return mirror(root.left, root.right);
    }

    private boolean mirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null || a.val != b.val) return false;
        return mirror(a.left, b.right) && mirror(a.right, b.left);
    }
}

Verdict: Like Same Tree with the children crossed.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single node
  • Asymmetric structure with equal values

Mistakes people make

  • Comparing a.left with b.left (that's Same Tree).

Interview

Follow-up questions

Iteratively?