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

## Comments

## Post a Comment