101. Symmetric Tree

Intuition

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. This means that for every node in the left subtree, there should be a corresponding node in the right subtree with the same value, and their children should also be mirror reflections of each other.

Approach

1. Base Case: - If the root is None, the tree is symmetric by definition.
2. Recursive Helper Function: - The helper function checks if two subtrees are mirrors of each other. - Base Cases: - If both nodes are None, they are symmetric. - If only one of the nodes is None, they are not symmetric. - If the values of the two nodes are different, they are not symmetric. - Recursive Case: - Recursively check if the left subtree of the first node is a mirror of the right subtree of the second node and the right subtree of the first node is a mirror of the left subtree of the second node.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the binary tree. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).

Code

C++

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return helper(root->left, root->right);
    }

private:
    bool helper(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr && root2 == nullptr) return true;
        if (root1 == nullptr || root2 == nullptr) return false;
        if (root1->val != root2->val) return false;
        return helper(root1->left, root2->right) && helper(root1->right, root2->left);
    }
};

Python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.helper(root.left, root.right)

    def helper(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None and root2 is None:
            return True
        if root1 is None or root2 is None:
            return False
        if root1.val != root2.val:
            return False
        return self.helper(root1.left, root2.right) and self.helper(root1.right, root2.left)

Java

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

    private boolean helper(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        return helper(root1.left, root2.right) && helper(root1.right, root2.left);
    }
}

JavaScript

var isSymmetric = function (root) 
{
    if (!root) return true;

    function helper(root1, root2) 
    {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val !== root2.val) return false;
        return helper(root1.left, root2.right) && helper(root1.right, root2.left);
    }

    return helper(root.left, root.right);
};