Problem Statement

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

Examples

Example 1:

Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: True

Example 2:

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

Exaplanation: When a straight line is drawn through the root node and the tree is folded around it, the rightmost node 3 is overlapped with null node and the node 3 present at left of root node is overlapped with null nodes.
So both node 3 in tree does not show symmetric behaviour.

Example 3:

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

Different Approaches

1️⃣ Recursive Approach

Intuition:

A tree is considered symmetric if its structure exhibits a mirroring pattern, where the left and right subtrees of each node are either identical or mirror images of each other. To verify the symmetry of a tree recursively, begin by comparing the root node's left and right subtrees. Then, for each pair of subtrees, ensure that the left child of the left subtree is a mirror image of the right child of the right subtree, and similarly, the right child of the left subtree mirrors the left child of the right subtree. This mirroring must be consistent throughout the entire tree to confirm its symmetry.

Approach:

1. First, check if the tree is empty by verifying if the root node is null. If the tree is empty, return true because an empty tree is symmetric by default.
2. If the tree is not empty, invoke a utility function, passing the left and right subtrees of the root node. This function will handle the recursive checks necessary to determine symmetry.
3. The base case in the recursive function occurs when both the left and right subtrees are null, in which case the function should return true. However, if only one subtree is null while the other is not, return false, as this indicates asymmetry.
4. For each node, compare the values of the current nodes from the left and right subtrees. Recursively check whether the left subtree of the left node mirrors the right subtree of the right node and vice versa. Continue these recursive comparisons until all corresponding nodes have been evaluated. If every comparison holds true, the tree is symmetric, and the function should return true. If any comparison fails, the function will return false, indicating that the tree is not symmetric.

Dry Run:

Code:

// Definition for a binary tree node.
  struct TreeNode {
      int data;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
  };
 

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true; // An empty tree is symmetric
        }
        return symmetry(root->left, root->right);
    }

private:
    bool symmetry(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {
            return true; // Both nodes are null, so symmetric
        }

        if (left == nullptr || right == nullptr) {
            return false; // One of the nodes is null, so not symmetric
        }

        if (left->data != right->data) {
            return false; // The values of the nodes do not match, so not symmetric
        }

        // Recursively check the children of the nodes
        return symmetry(left->left, right->right) && symmetry(left->right, right->left);
    }
};

// Example usage
int main() {
    Solution solution;

    // Create a sample tree: 1, 2, 2, 3, 4, 4, 3
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);

    // Test the symmetric tree
    std::cout << std::boolalpha << solution.isSymmetric(root) << std::endl; // Output: true

    return 0;
}

Complexity Analysis:

• Time complexity: O(N) This is because there are N number of nodes in the binary tree each node is traversed once to check for symmetry.
• Space complexity: O(h) This is because the maximum depth of the recursion stack is equal to the height of the tree.