Symmetric Tree

Problem Statement

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

Approach

The problem can be solved using a recursive approach. The idea is to check if the left subtree of the root is a mirror of the right subtree of the root.

To check if two trees are a mirror of each other:

1. If either of the trees is null, then both trees should be null.
2. Check if the values of the root nodes of both trees are equal.
3. Check if the right subtree of the left tree is a mirror of the left subtree of the right tree.
4. Check if the left subtree of the left tree is a mirror of the right subtree of the right tree.

Implementation

Here is a java implementation of the above approach:

public boolean isSymmetric(TreeNode root) {
    if(null == root){
        return true;
    }   
    return check(root.left, root.right);
}

private boolean check(TreeNode left, TreeNode right){
    if(null == left || null == right){
        return null == left && null == right;
    }

    return left.val == right.val
           && check(left.left, right.right)
           && check(left.right, right.left);
}

Complexity Analysis

The time complexity for this approach is $O(N)$, where $N$ is the number of nodes in the binary tree. The space complexity is $O(N)$ as well, considering the recursive stack space.