### 101. Symmetric Tree (Recursion)

Blog Post: Symmetric Tree

# 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!