LeetCode Problem Link

Problem Description:

Given the root of a binary tree, check whether it is symmetric around its center. A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.

Example 1:

root = [1,2,2,3,4,4,3]
Output: true

Example 2:

root = [1,2,2,null,3,null,3]
Output: false

Approach Analysis

To determine whether a binary tree is symmetric, we need to compare whether the left subtree and right subtree are mirror images of each other. The key insight is that we are not simply comparing left and right child nodes, but rather comparing whether the entire subtrees are symmetric.

During traversal, we need to examine both subtrees simultaneously. The comparison involves checking outer nodes against outer nodes and inner nodes against inner nodes.

Recursive Solution

The recursive approach requires a helper function that takes two tree node pointers as parameters. This function will compare the two subtrees and return a boolean indicating whether they are mirror images.

Step 1: Define the Recursive Function

The helper function needs to compare two subtrees, so we define it as follows:

bool isMirror(TreeNode* p, TreeNode* q) {}

Step 2: Establish Base Cases

When comparing two subtrees, five distinct scanarios must be handled:

1. Left subtree is null, right subtree is not null → Not symmetric
2. Left subtree is not null, right subtree is null → Not symmetric
3. Both subtrees are null → Symmetric
4. Both subtrees exist but node values differ → Not symmetric
5. Both subtrees exist with matching values → Continue comparison

// Left subtree exists, right subtree is missing
if (p != nullptr && q == nullptr) return false;
// Left subtree is missing, right subtree exists
if (p == nullptr && q != nullptr) return false;
// Both subtrees are empty
if (p == nullptr && q == nullptr) return true;
// Node values do not match
if (p->val != q->val) return false;

Step 3: Define Recursive Logic

When both subtrees have matching root values, we must continue comparing their children. For symmetry, the outer children (left subtree's left child and right subtree's right child) must match, as must the inner children (left subtree's right child and right subtree's left child).

// Compare outer nodes: left subtree's left with right subtree's right
bool outerMatch = isMirror(p->left, q->right);
// Compare inner nodes: left subtree's right with right subtree's left
bool innerMatch = isMirror(p->right, q->left);
// Both outer and inner comparisons must succeed
return outerMatch && innerMatch;

Complete Recursive Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isMirror(TreeNode* p, TreeNode* q) {
        // Case 1: One subtree exists while the other does not
        if (p != nullptr && q == nullptr) return false;
        if (p == nullptr && q != nullptr) return false;
        
        // Case 2: Both subtrees are empty
        if (p == nullptr && q == nullptr) return true;
        
        // Case 3: Node values differ
        if (p->val != q->val) return false;
        
        // Case 4: Recursive comparison of child nodes
        bool outerCheck = isMirror(p->left, q->right);
        bool innerCheck = isMirror(p->right, q->left);
        return outerCheck && innerCheck;
    }

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return isMirror(root->left, root->right);
    }
};

Iterative Solution Using Breadth-First Search

Instead of recursion, we can use a queue to perform level-order traversal while simultaneously comparing node pairs. This approach processes nodes in pairs, ensuring symmetric comparison at each level.

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        std::queue<TreeNode*> nodeQueue;
        nodeQueue.push(root->left);
        nodeQueue.push(root->right);
        
        while (!nodeQueue.empty()) {
            TreeNode* first = nodeQueue.front(); nodeQueue.pop();
            TreeNode* second = nodeQueue.front(); nodeQueue.pop();
            
            // Both nodes are null - continue checking remaining pairs
            if (first == nullptr && second == nullptr) continue;
            
            // Asymmetry detected: one null, or values don't match
            if (first == nullptr || second == nullptr || first->val != second->val) {
                return false;
            }
            
            // Enqueue outer children for comparison
            nodeQueue.push(first->left);
            nodeQueue.push(second->right);
            // Enqueue inner children for comparison
            nodeQueue.push(first->right);
            nodeQueue.push(second->left);
        }
        return true;
    }
};

Iterative Solution Using Depth-First Search with Stack

A stack-based approach mirrors the BFS solution but processes nodes in depth-first order. We push node pairs onto the stack and compare them as they are popped.

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        std::stack<TreeNode*> nodeStack;
        nodeStack.push(root->left);
        nodeStack.push(root->right);
        
        while (!nodeStack.empty()) {
            TreeNode* first = nodeStack.top(); nodeStack.pop();
            TreeNode* second = nodeStack.top(); nodeStack.pop();
            
            if (first == nullptr && second == nullptr) continue;
            
            if (first == nullptr || second == nullptr || first->val != second->val) {
                return false;
            }
            
            nodeStack.push(first->left);
            nodeStack.push(second->right);
            nodeStack.push(first->right);
            nodeStack.push(second->left);
        }
        return true;
    }
};

Complexity Analysis

All three approaches have the same time and space complexity:

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
• Space Complxeity: O(h) for the recursive and stack-based solutions, where h is the tree height (due to call stack or explicit stack). For the queue-based solution, space complexity is O(w), where w is the maximum width of the tree.