Symmetric Tree in C++ (Time Complexity: O(n))

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

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

Constraints:

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

Follow up: Could you solve it both recursively and iteratively?

Understanding the Problem

The core challenge of this problem is to determine if a binary tree is symmetric around its center. This means that the left subtree is a mirror reflection of the right subtree. This problem is significant in various applications such as validating data structures, ensuring balanced operations in algorithms, and more.

Potential pitfalls include misunderstanding the symmetry concept, especially when dealing with null nodes. A common misconception is that if the left and right subtrees have the same structure, they are symmetric, but their values must also mirror each other.

Approach

To solve this problem, we can use two main approaches: recursive and iterative.

Recursive Approach

The recursive approach involves checking if the left and right subtrees are mirrors of each other. This can be done by comparing the left child of the left subtree with the right child of the right subtree and vice versa.

Iterative Approach

The iterative approach uses a queue to perform a level-order traversal, ensuring that corresponding nodes in the left and right subtrees are mirrors of each other.

Algorithm

Recursive Algorithm

Define a helper function that takes two nodes as arguments.
Check if both nodes are null; if so, return true.
If only one of the nodes is null, return false.
Check if the values of the two nodes are equal.
Recursively check the left child of the first node with the right child of the second node and the right child of the first node with the left child of the second node.

Iterative Algorithm

Use a queue to store pairs of nodes to be compared.
Initialize the queue with the left and right children of the root.
While the queue is not empty, dequeue a pair of nodes.
Check if both nodes are null; if so, continue.
If only one of the nodes is null, return false.
Check if the values of the two nodes are equal.
Enqueue the left child of the first node with the right child of the second node and the right child of the first node with the left child of the second node.

Code Implementation

Recursive Solution


// 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 isSymmetric(TreeNode* root) {
        return isMirror(root, root);
    }

private:
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        return (t1->val == t2->val)
            && isMirror(t1->right, t2->left)
            && isMirror(t1->left, t2->right);
    }
};

Iterative Solution


#include 

// 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 isSymmetric(TreeNode* root) {
        if (!root) return true;
        std::queue q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode* t1 = q.front(); q.pop();
            TreeNode* t2 = q.front(); q.pop();
            if (!t1 && !t2) continue;
            if (!t1 || !t2) return false;
            if (t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        return true;
    }
};

Complexity Analysis

Both the recursive and iterative solutions have a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited once. The space complexity for the recursive solution is O(h), where h is the height of the tree, due to the recursion stack. For the iterative solution, the space complexity is O(n) due to the queue used for level-order traversal.

Edge Cases

Potential edge cases include:

A tree with only one node (should return true).
A tree where all nodes have the same value but different structures (should return false).
A tree with null nodes interspersed (should handle null nodes correctly).

Testing

To test the solution comprehensively, consider the following test cases:

A perfectly symmetric tree.
A tree that is not symmetric.
A tree with only one node.
A tree with null nodes.

Using a testing framework like Google Test can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Understand the problem requirements and constraints thoroughly.
Break down the problem into smaller, manageable parts.
Consider both recursive and iterative solutions to find the most efficient approach.
Practice solving similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the symmetric tree problem is crucial for mastering tree-based algorithms. By practicing both recursive and iterative approaches, you can enhance your problem-solving skills and prepare for more complex challenges.

Additional Resources

For further reading and practice, consider the following resources: