Problem Statement

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

LeetCode:

• Symmetric Tree

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 ≤ Node.val ≤ 100

Examples

Example 1:

Input: root = [1, 2, 2, 3, 4, 4, 3]
    1
   / \
  2   2
 / \ / \
3  4 4  3

Output: true

Explanation:
This tree is symmetric because:
    The left subtree of node 1 is [2, 3, 4].
    The right subtree of node 1 is [2, 4, 3], which is a mirror reflection of the left subtree.

Example 2:

Input: root = [1, 2, 2, null, 3, null, 3]

    1
   / \
  2   2
   \   \
    3   3

Output: false

Different Approaches

1️⃣ Recursive Approach:

Intuition:

isSymmetric(root):
    if root is null:
        return true
    return isMirror(root->left, root->right)

isMirror(left, right):
    if left is null and right is null:
        return true
    if left is null or right is null or left->val != right->val:
        return false
    return isMirror(left->left, right->right) && isMirror(left->right, right->left)

Code Implementation:

class Solution {
public:
    // Function to check if a binary tree is symmetric
    bool isSymmetric(TreeNode* root) {
        // If the tree is empty, it is symmetric by definition
        if (!root)
            return true;
        // Call the helper function to check if the left and right subtrees are mirrors of each other
        return isMirror(root->left, root->right);
    }
    
    // Helper function to check if two subtrees are mirrors of each other
    bool isMirror(TreeNode* left, TreeNode* right) {
        // If both nodes are null, they are mirrors of each other
        if (!left && !right)
            return true;
        // If one of the nodes is null or their values are different, they are not mirrors
        if (!left || !right || left->val != right->val)
            return false;
        // Recursively check if the left subtree of the left node is a mirror of the right subtree of the right node
        // and if the right subtree of the left node is a mirror of the left subtree of the right node
        return isMirror(left->left, right->right) && isMirror(left->right, right->left);
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • The time complexity of the recursive approach is O(n), where n is the number of nodes in the binary tree.
  • This is because we traverse each node once, performing constant-time operations at each node.
• Space Complexity:
  • The space complexity of the recursive approach is O(h), where h is the height of the binary tree.
  • This is due to the recursive calls consuming space on the call stack.
  • In the worst case, when the tree is skewed, the height of the tree can be equal to the number of nodes, resulting in O(n) space complexity.

2️⃣ Iterative Approach using Queue

Intuition:

isSymmetric(root):
    if root is null:
        return true
    queue <- [root->left, root->right]
    while queue is not empty:
        left <- queue.front
        queue.pop
        right <- queue.front
        queue.pop
        if left is null and right is null:
            continue
        if left is null or right is null or left->val != right->val:
            return false
        queue.push(left->left)
        queue.push(right->right)
        queue.push(left->right)
        queue.push(right->left)
    return true

Code Implementation:

class Solution {
public:
    // Function to check if a binary tree is symmetric
    bool isSymmetric(TreeNode* root) {
        // If the tree is empty, it is symmetric by definition
        if (!root)
            return true;
        // Create a queue for level order traversal
        queue<TreeNode*> q;
        // Enqueue the left and right children of the root
        q.push(root->left);
        q.push(root->right);
        
        // Continue until the queue is empty
        while (!q.empty()) {
            // Dequeue two nodes at a time
            TreeNode* left = q.front();
            q.pop();
            TreeNode* right = q.front();
            q.pop();
            
            // If both nodes are null, continue to the next pair of nodes
            if (!left && !right)
                continue;
            // If one of the nodes is null or their values are different, the tree is not symmetric
            if (!left || !right || left->val != right->val)
                return false;
            // Enqueue the left child of the left node and the right child of the right node
            q.push(left->left);
            q.push(right->right);
            // Enqueue the right child of the left node and the left child of the right node
            q.push(left->right);
            q.push(right->left);
        }
        // If the loop completes without returning false, the tree is symmetric
        return true;
    }
};

Complexity Analysis:

• Time Complexity:
  • The time complexity of the iterative approach is O(n), where n is the number of nodes in the binary tree.
  • In the worst case, we traverse all nodes of the binary tree once.
• Space Complexity:
  • The space complexity of the iterative approach is O(n), where n is the number of nodes in the binary tree.
  • This is because we use a queue data structure to perform level-order traversal of the tree, which can store up to O(n) nodes in the worst case.
  • Additionally, the space complexity is not affected by the shape of the tree since we traverse it iteratively without using additional recursive calls.