# Symmetric Tree LeetCode Solution Leetcode Solution

Difficulty Level Easy
BllombergViews 156

## Problem Statement

The Symmetric Tree LeetCode Solution – “Symmetric Tree” states that given the root of the binary tree and we need to check if the given binary tree is a mirror of itself(symmetric around its center) or not? If Yes, we need to return true otherwise, false.

## Example:

Note that nodes with the same color have the same node value. The binary tree is a Symmetric Tree.

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

Explanation:

• Check the above diagram for a better understanding.
`Input:  root = [1,2,2,null,3,null,3]`
`Output: false`

Explanation:

• Check the above diagram for a better understanding.

## Approach

### Idea:

1. The main idea to solve this problem is to use Recursion.
2. Now, a tree is called symmetric if the left subtree must be a mirror reflection of the right subtree.
3. Also, Two trees are said to be a mirror with respect to each other if:
1. Their roots are of the same value.
2. The right subtree of each tree is a mirror reflection of the left subtree of another tree.
4. So, perform the recursion with the following cases:
1. For the base case:
• If both root nodes are null pointers, return true.
• If exactly one of them is a null node, return false.
2. In general:
• Root nodes must have the same value and,
• The left subtree and right subtree must be the mirror reflection with respect to each other.
• So, return true if the root node’s values are the same and left as well as right subtrees are symmetric.

## Code

### Symmetric Tree Leetcode C++ Solution:

```class Solution {
public:
bool check(TreeNode* root1,TreeNode* root2){
if(root1==nullptr or root2==nullptr){
return root1==root2;
}
return root1->val==root2->val and check(root1->left,root2->right) and check(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};```

### Symmetric Tree Leetcode Java Solution:

```class Solution {
private boolean check(TreeNode root1,TreeNode root2){
if(root1==null || root2==null){
return root1==root2;
}
return root1.val==root2.val && check(root1.left,root2.right) && check(root1.right,root2.left);
}
public boolean isSymmetric(TreeNode root) {
return check(root,root);
}
}```

## Complexity Analysis for Symmetric Tree Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N) since we traverse the entire input tree once where N = the total number of nodes in the tree.

### Space Complexity

The space complexity of the above code is O(N) [considering recursive calls also]. The number of recursive calls is bounded by the height of the tree and in the worst case, the tree can be linear. Hence, Space Complexity is O(N).

Translate »