Leetcode - 101. Symmetric Tree

Checking if a binary tree is symmetric is a classic recursive problem in data structures. In this post, let’s break it down into simple steps, understand the thought process, and see how recursion makes the solution elegant and intuitive.

🧠 What Does “Symmetric” Mean?

A binary tree is symmetric if the left and right subtrees are mirror images of each other.

Here’s an example of a symmetric tree:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

And here's an asymmetric one:

        1
       / \
      2   2
       \   \
        3   3

In the second tree, the structure and values don't mirror each other — hence it’s not symmetric.

🛠️ Approach: Mirror Comparison via Recursion

To check symmetry, we write a helper function isMirror(left, right) that checks if two trees are mirror images of each other.

🔄 Mirror logic:

• Both left and right are null: ✅ symmetric
• One is null, the other isn’t: ❌ not symmetric
• Values don’t match: ❌ not symmetric
• If values match: recursively compare:
  • left.left with right.right
  • left.right with right.left

✅ JavaScript Code

/**
 * Definition for a binary tree node.
 * 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) {
    if (root == null) {
        return true;
    }
    return isMirror(root.left, root.right);
};

const isMirror = (left, right) => {
    if (left == null && right == null) {
        return true;
    } else if (left == null || right == null) {
        return false;
    } else {
        if (left.val !== right.val) {
            return false;
        }
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
};

🔍 Visualization

You can think of the mirror like a fold line in the middle. You compare:

left.left <--> right.right  
left.right <--> right.left

At every level of recursion, you "criss-cross" compare nodes.

⏱️ Time & Space Complexity

Time Complexity: O(n)

• We visit each node once, where n is the total number of nodes in the tree.

Space Complexity: O(h)

• Due to the recursion stack, where h is the height of the tree.
• In the worst case (skewed tree), this can be O(n), but for a balanced tree, it would be O(log n).

🤔 Why This Approach Rocks

• No need for extra arrays or queues — it's pure, elegant recursion.
• Mirrors real-world logic: if the tree mirrors itself at each level, it's symmetric.

🧪 Pro Tip: Test Cases

// Symmetric
Input: [1,2,2,3,4,4,3] → Output: true

// Asymmetric
Input: [1,2,2,null,3,null,3] → Output: false

💬 Final Thoughts

This is one of those problems that looks tricky at first but becomes simple once you "see the mirror." Recursion shines here — you just delegate the symmetry check down the tree, trusting each level to do its part.