101. Symmetric Tree (Recursion)

101. Symmetric Tree

Problem Description

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

Solution

To solve this problem, we can use a recursive approach. We define a helper function, isMirror, that takes in two tree nodes and checks if they are mirrors of each other.

First, we check if both nodes are null. If they are, it means they are symmetric, so we return true (base case).

Next, we check if either one of the nodes is null. If only one of them is null, it means they are not symmetric, so we return false (base case).

If both nodes are not null, we compare their values. If the values are not equal, they are not symmetric, so we return false.

Finally, if the values are equal, we recursively call isMirror on the left and right subtrees, swapping the nodes between the trees. We check if both recursive calls return true to determine if the entire tree is symmetric.

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

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node once to check for symmetry.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the tree can be skewed, resulting in a space complexity of O(n). However, in a balanced tree, the space complexity is O(log n).

Example

Let's consider the following binary tree:

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

The tree above is symmetric, as each node has a mirrored counterpart. We can use the provided code to check if the tree is symmetric:

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

Solution solution;
bool isSymmetric = solution.isSymmetric(root);
    

After executing the code, the value of isSymmetric will be true since the tree is symmetric.

Conclusion

In this blog post, we explored the problem of determining whether a binary tree is symmetric. We discussed a recursive solution and provided the corresponding C++ implementation. Additionally, we analyzed the time and space complexities of the solution and demonstrated an example usage.

Feel free to try out the code with different binary trees to check for symmetry!