How to Check If a Binary Tree Is Symmetric in O(n) Time

Problem Description

Given a binary tree, determine whether it is a mirror of itself (i.e., symmetric around its center). For example, the tree represented by [1,2,2,3,4,4,3] is symmetric, while the tree [1,2,2,null,3,null,3] is not.

Solution Idea

Key Points

Tag: DFS

Recursive termination conditions:

Both nodes are null → return true Only one node is null → return false Recursive process:

Check if the current node values are equal.

Recursively verify that the right subtree of node A mirrors the left subtree of node B.

Recursively verify that the left subtree of node A mirrors the right subtree of node B.

Short‑circuit behavior: the logical && operator stops evaluation as soon as a false is encountered, avoiding unnecessary recursive calls.

Time complexity: O(n), where n is the number of nodes.

Algorithm Animation

Reference Implementation (Java)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
    }
}