Symmetric Tree easy

Problem Statement

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

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

Steps

1. Recursive Approach: We can solve this problem recursively. The core idea is that a tree is symmetric if its left subtree is a mirror image of its right subtree.

2. Base Cases:

   • An empty tree is symmetric.
   • A tree with only one node is symmetric.

3. Recursive Step:

   • Compare the values of the left and right subtrees' root nodes. If they are different, the tree is not symmetric.
   • Recursively check if the left subtree's right subtree is a mirror of the left subtree's left subtree AND the right subtree's left subtree is a mirror of the right subtree's right subtree.

4. Iterative Approach (Optional): We can also use an iterative approach using a queue to perform a level order traversal. We add pairs of nodes (left, right) from each level to the queue and compare their values. If they differ, the tree isn't symmetric.

Explanation

The recursive approach elegantly mirrors the definition of symmetry. If the root values match, we recursively check the symmetry of the swapped subtrees (left.right, right.left and left.left, right.right). This continues until we reach null nodes (empty subtrees) or find a mismatch. The iterative approach provides an alternative that might be slightly more efficient in some cases due to the reduced function call overhead of recursion. However, the recursive solution is often considered more readable and easier to understand.

Code (Java - Recursive Approach)

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true; // Empty tree is symmetric
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true; // Both null, symmetric
        if (left == null || right == null) return false; // One null, not symmetric
        if (left.val != right.val) return false; // Values mismatch, not symmetric

        // Recursive check for mirror symmetry of subtrees
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

Code (Java - Iterative Approach)

import java.util.*;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;

            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

Complexity

Recursive Approach:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at most once.
• Space Complexity: O(H) in the worst case, where H is the height of the tree (due to recursive call stack). In a balanced tree, H = log(N). In a skewed tree, H = N.

Iterative Approach:

• Time Complexity: O(N)
• Space Complexity: O(W), where W is the maximum width of the tree. In a balanced tree, W = N. In a skewed tree, W = 1. This is generally better than the recursive approach's space complexity in the worst case.