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'll use a recursive function to check for symmetry.
2. Base Case: If both subtrees are null, they are symmetric (empty trees are symmetric). If only one is null, they are not symmetric.
3. Recursive Step: Compare the values of the root nodes of the left and right subtrees. If they are different, the tree is not symmetric. If they are the same, recursively check the symmetry of the left subtree's left child and the right subtree's right child, and the left subtree's right child and the right subtree's left child.

Explanation

A tree is symmetric if its left subtree is a mirror image of its right subtree. This means that the value of the left child of the root must equal the value of the right child of the root, and the left subtree of the left child must be a mirror image of the right subtree of the right child, and the right subtree of the left child must be a mirror image of the left subtree of the right child, and so on recursively. The recursive function elegantly handles this mirroring comparison.

Code

using System;

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

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

    private bool IsMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true; // Base case: both null
        if (left == null || right == null) return false; // Base case: one null, one not null

        // Recursive step: check values and recursively check subtrees
        return (left.val == right.val) && 
               IsMirror(left.left, right.right) && 
               IsMirror(left.right, right.left);
    }
}

Complexity

• 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), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂(N).