Symmetric Tree easy

Problem Statement

Given the root of a binary tree, check if 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 to Solve:

  1. Recursive Approach: We'll use a recursive helper function to compare subtrees.

  2. Base Cases:

    • If both nodes are null, they are symmetric (return true).
    • If only one node is null, they are not symmetric (return false).
    • If the values of the nodes are different, they are not symmetric (return false).

  3. Recursive Calls: Recursively compare the left subtree of the first node with the right subtree of the second node, and the right subtree of the first node with the left subtree of the second node. This mirrors the comparison.

  4. Return Value: The helper function returns true only if all recursive comparisons return true; otherwise, it returns false.

Explanation:

The solution uses recursion to efficiently check for symmetry. The core idea is that a tree is symmetric if its left and right subtrees are mirror images of each other. We recursively compare nodes mirroring their positions in the left and right subtrees. If at any point the values or structures don't match, the tree is not symmetric.

Code (TypeScript):

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function isSymmetric(root: TreeNode | null): boolean {
    function helper(left: TreeNode | null, right: TreeNode | null): boolean {
        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 different, not symmetric

        // Recursive calls for mirroring comparison
        return helper(left.left, right.right) && helper(left.right, right.left);
    }

    return helper(root, root); // Start comparison from the root
}

Complexity Analysis:

  • 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 could be equal to N, but in a balanced tree, H is logâ‚‚(N).