Symmetric Tree

Easy
1863.

Symmetric Tree

Symmetric Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft, Bloomberg and LinkedIn interviews.

Given the root of a binary tree, return true if the tree is a mirror image of itself around its centre line — its left subtree is the reflection of its right subtree, in shape and in values — and false otherwise.

Example 1

Input
root = [1,2,2,3,4,4,3]
Output
true
Explanation
Reflecting the left subtree `2 → (3, 4)` gives `2 → (4, 3)`, which is exactly the right subtree.

Example 2

Input
root = [1,2,2,null,3,null,3]
Output
false
Explanation
Both 3s are right children; a mirror image would need one of them on the left.

Example 3

Input
root = [7]
Output
true

Constraints

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

Follow-up: Can you solve it both recursively and iteratively?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Symmetric Tree — Solution in Python, Java & C++

Symmetric Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Symmetric Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft, Bloomberg and LinkedIn interviews.

Problem statement

Given the root of a binary tree, return true if the tree is a mirror image of itself around its centre line — its left subtree is the reflection of its right subtree, in shape and in values — and false otherwise.

Example 1

Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: Reflecting the left subtree `2 → (3, 4)` gives `2 → (4, 3)`, which is exactly the right subtree.

Example 2

Input: root = [1,2,2,null,3,null,3]
Output: false
Explanation: Both 3s are right children; a mirror image would need one of them on the left.

Example 3

Input: root = [7]
Output: true

Constraints

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

Follow-up: Can you solve it both recursively and iteratively?

Hints for Symmetric Tree

  1. Hint 1

    Symmetry is a relation between two subtrees: the root's left and right.

  2. Hint 2

    Two trees a and b are mirrors when their roots match, a.left mirrors b.right, and a.right mirrors b.left.

  3. Hint 3

    Iteratively, put pairs (a, b) on a queue and push (a.left, b.right) and (a.right, b.left) for each matching pair.

How to solve Symmetric Tree

A tree is symmetric when its left subtree is the mirror of its right subtree. Check that with a helper mirror(a, b) that walks the two subtrees in opposite directions at the same time.

Approach

  1. Return mirror(root.left, root.right).
  2. mirror(a, b): if both are null return true; if exactly one is null return false.
  3. If a.val != b.val return false.
  4. Return mirror(a.left, b.right) && mirror(a.right, b.left).

Why it works

Reflecting a tree swaps left and right at every level, so the node at the position reached by a path of left/right turns on one side must equal the node reached by the opposite turns on the other. The helper compares exactly those position pairs, outer with outer and inner with inner.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth (a queue of pairs uses O(width) instead)

Pitfalls

  • Comparing a.left with b.left checks equality, not reflection.
  • Equal level-order value lists are not enough when nulls are ignored — positions matter.

Reference solution

Python

from typing import Optional

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def mirror(a, b):
        if a is None or b is None:
            return a is b
        return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)

    return root is None or mirror(root.left, root.right)

Java

public static boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}

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

C++

bool mirrorPair(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;
    return a->val == b->val && mirrorPair(a->left, b->right) && mirrorPair(a->right, b->left);
}

bool isSymmetric(TreeNode* root) {
    return !root || mirrorPair(root->left, root->right);
}

JavaScript

var isSymmetric = function(root) {
    return root === null || mirror(root.left, root.right);
};

var mirror = function(a, b) {
    if (a === null || b === null) return a === b;
    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)