# Check if Binary Tree is Symmetric or Not

Check if Binary Tree is Symmetric or Not” is a basic problem based on tree data structure. Here, we are given a binary tree and our task is to write a program to check if given binary tree have symmetric structure or not.

A Binary Tree is having symmetric structure if left subtree and right subtree are mirror image of each other, irrespective of node value.

We have already discussed to check if two binary trees are mirror tree of each other or not. Here, also, we will use same technique to check symmetry of tree.

A Binary Tree is Symmetric if it holds following conditions:

1. Both Left subtree and right subtree are empty or non-empty.
2. Left Subtree is mirror image of right subtree, irrespective of data.
3. Right Subtree is mirror image of left subtree, irrespective of data.

#### C++ Program to Check if Binary Tree is Symmetric or Not is as follows:

```/* C++ Program to Check if Binary Tree is Symmetric or Not */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to Check if Binary Tree is Symmetric or Not */
bool checkSymmetry(Node *root1, Node *root2)
{
/* Base Case1: If both Subtrees are Empty */
if(root1 == NULL && root2 == NULL)
return true;

/* Base Case2: If one subtree is empty and other not */
if(root1 == NULL || root2 == NULL)
return false;

/*
If Both are Non-Empty, Recursively compare left subtree
with right subtree and vice-versa
*/
return (root1 != NULL && root2 != NULL) &&
checkSymmetry(root1 -> left, root2 -> right) &&
checkSymmetry(root1 -> right,root2 -> left);
}

int main()
{
/* Creating a Binary trees and inserting some nodes in it */
Node *root = NULL;

root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);

/* Calling function to Check if Binary Tree is Symmetric or Not */
if(checkSymmetry(root -> left, root -> right) == true)
{
cout<<"Given Binary Tree is Symmetric Tree!!";
}
else
{
cout<<"Given Binary Tree is not Symmetric Tree!!";
}
}

```

OUTPUT:

`Given Binary Tree is Symmetric Tree!!`

Related Posts: