# Symmetric Tree

In this article, we are going to see how to find whether a tree is symmetric tree or not? This problem can be featured in the interview coding rounds.
Submitted by Radib Kar, on January 14, 2019

Problem statement:

Given a binary Tree, check whether the tree is symmetric or not.

Input Example:

```For example
1
/ \
2   2
/ \ / \
3  4 4  3

The above tree is symmetric
1
/ \
2   2
\   \
4    4
The above tree is not

```

Solution

## Symmetric tree

A binary tree is said to be symmetric, if a vertical axis through the root cuts the tree in two mirror subtrees. That means the right child & left child of root are two mirror trees.

Algorithm:

Earlier, we have discussed how two check mirror trees? Kindly refer there for more detailed analysis.

In this case we are to check whether the tree is symmetric or not, which can be done via checking whether root's children are mirror trees or not?

```FUNCTION isSymmetric(Tree Node* root)
1.  Check for base cases
IF root==NULL //if root is NULL
Return true;
IF root->left==NULL &&root->right==NULL //if both child is NULL
Return true;
IF root->left==NULL || root->right==NULL //if only one child is NULL
Return false;
2.  check whether left & right subtrees are mirror of each other or not
Return check(root->left,root->right);
END FUNCTION
```
```FUNCTION Check(Tree Node* root1, Tree Node* root2)
a.  Check base cases
If root1==NULL && root2==NULL
Then it's mirror tree, return true;
If root1==NULL || root2==NULL
Then it's not a mirror tree, return false
Because one root is NULL whether another is not.
(Both can't be NULL here, since already checked before)
If root1->data != root2->data
Then it's not a mirror tree, return false.
Because roots are different & thus can't be mirror image of other
b.  Recursively check for sub-trees
Return (Check (root1->left, root2->right) &&Check(root1->right,root2->left));
END FUNCTION
```

Example with explanation

```For the example:
1
/ \
2   2
/ \ / \
3  4 4  3

At the main function:
It calls isSymmetric(1)
-----------------------------------------------------------

isSymmetric(1):
Base cases are not met
It calls check(1->left, 1->right)

Root1=2(1->left) and Root2=2(1->right)
It calls check (2, 2)
-----------------------------------------------------------

check (2, 2):
2->left =3 and 2->right=4 in case of tree1
2->left =4 and 2->right=3 in case of tree2
No base cases are satisfied thus it returns,
(check ( 3, 3) && check ( 4, 4))
Call to check ( 3, 3) and check ( 4, 4)
-----------------------------------------------------------

check (3, 3):(call at check (2, 2))
3->left =NULL and 3->right=NULL in case of tree1
3->left =NULL and 3->right=NULL in case of tree2
No base cases are satisfied thus it returns,
(check (NULL, NULL) &&check (NULL, NULL))
Call to check (NULL, NULL) and check (NULL, NULL))
-----------------------------------------------------------

check (4, 4): (call at check (2, 2))
4->left =NULL and 4->right=NULL in case of tree1
4->left =NULL and 4->right=NULL in case of tree2
No base cases are satisfied thus it returns,
(check (NULL, NULL) &&check (NULL, NULL))
Call to check (NULL, NULL) &&check (NULL, NULL)
-----------------------------------------------------------

check (NULL, NULL): (call at check (3, 3))
Base case matches and returns 1.
-----------------------------------------------------------

check (NULL, NULL): (call at check (3, 3))
Base case matches and returns 1.
-----------------------------------------------------------

check (NULL, NULL): (call at check (4, 4))
Base case matches and returns 1.
-----------------------------------------------------------

check (NULL, NULL): (call at check (4, 4))
Base case matches and returns 1.
-----------------------------------------------------------

Thus at isSymmetric(1),
check (2, 2) returns:
=   check ( 3, 3) &&check ( 4, 4)
=   ((check (NULL, NULL)&&check (NULL, NULL))
&&((check (NULL, NULL)&&check (NULL, NULL))
=   ((1 && 1)) && (1 && 1))
=   1

Thus at main it returns 1
So it's a symmetric tree
```

C++ implementation

```#include<bits/stdc++.h>
using namespace std;

// TreeNode node type
class TreeNode{
public:
int val;           //value
TreeNode *left;    //pointer to left child
TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(int data)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = data;
node->left = NULL;
node->right = NULL;

return(node);
}

// function to check mirror trees
bool check(TreeNode* root1,TreeNode* root2){
// base cases
//if both root is NULL, then it's mirror tree
if(!root1 && !root2)
return true;
//if one is NULL & other is not
//then it's not mirror tree
if(!root1 || !root2)
return false;
//if root data are different it's not mirror tree
if(root1->val!=root2->val)
return false;
//check for subtrees
return (check(root1->left,root2->right)&&check(root1->right,root2->left));
}

bool isSymmetric(TreeNode* root) {
//base cases
if(!root)
return true;
if(!root->left && !root->right)
return true;
if(!root->left || !root->right)
return false;
//check whether left & right subtrees
//are mirror of each other or not
return check(root->left,root->right);
}

int main(){
cout<<"tree is built as per example\n";

TreeNode *root=newnode(1);
root->left= newnode(2);
root->right= newnode(2);
root->right->right=newnode(3);
root->right->left=newnode(4);
root->left->left=newnode(3);
root->left->right=newnode(4);

if(isSymmetric(root))
cout<<"It's a symmetric tree\n";
else
cout<<"It's not a symmetric tree\n";

return 0;
}
```

Output

```tree is built as per example
It's a symmetric tree
```