Problem Statement

Given a binary tree, determine if it is symmetric around its center. In other words, check if the left subtree is a mirror reflection of the right subtree.

Examples

Example 1:

Consider the following binary tree:

    1
   / \
  2   2
 / \ / \
3  4 4  3

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.

Different Approaches

1 Recursive Approach:

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)

2 Iterative Approach using Queue

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

1 Recursive Approach:

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);
    }
};

2 Iterative Approach using Queue:

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;
    }
};

Code Complexity Analysis

1 Recursive Approach:

• 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:

• 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.