Symmetric Tree

easy tree dfs recursion

Problem

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

Walk a pair of pointers (L, R) outward from the root. At each step compare values, then recurse on (L.left, R.right) and (L.right, R.left).

Inputlevel-order: [1, 2, 2, 3, 4, 4, 3]

Outputtrue

Outermost pair (2, 2) matches; next pairs (3, 3) and (4, 4) match too.

level-order ('_' for null)

def is_symmetric(root):
    def mirror(L, R):
        if L is None and R is None: return True
        if L is None or R is None: return False
        if L.val != R.val: return False
        return mirror(L.left, R.right) and mirror(L.right, R.left)
    return root is None or mirror(root.left, root.right)

function isSymmetric(root) {
  function mirror(L, R) {
    if (!L && !R) return true;
    if (!L || !R) return false;
    if (L.val !== R.val) return false;
    return mirror(L.left, R.right) && mirror(L.right, R.left);
  }
  return !root || mirror(root.left, root.right);
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || mirror(root.left, root.right);
    }
    private boolean mirror(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;
        if (L == null || R == null) return false;
        if (L.val != R.val) return false;
        return mirror(L.left, R.right) && mirror(L.right, R.left);
    }
}

bool mirror(TreeNode* L, TreeNode* R) {
    if (!L && !R) return true;
    if (!L || !R) return false;
    if (L->val != R->val) return false;
    return mirror(L->left, R->right) && mirror(L->right, R->left);
}
bool isSymmetric(TreeNode* root) {
    return !root || mirror(root->left, root->right);
}

Explanation

A tree is symmetric when its left half is a mirror image of its right half. So instead of checking one tree, we compare two pointers moving outward in opposite directions.

The helper mirror(L, R) compares a left-side node with the matching right-side node. They match if both are empty; they fail if only one is empty or their values differ. The key recursive step is comparing L.left with R.right and L.right with R.left — crossing over because a mirror flips left and right.

We kick it off by calling mirror(root.left, root.right) (an empty tree counts as symmetric). If every mirrored pair agrees all the way down, the tree is symmetric.

Example: [1,2,2,3,4,4,3]. The two 2s match. Then L.left = 3 is compared with R.right = 3, and L.right = 4 with R.left = 4. All pairs agree, so the answer is true.

Each node is checked once, giving O(n) time.

Time: O(n) Space: O(h) recursion depth