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.
![Check if Binary Tree is Symmetric or Not](https://www.helpmestudybro.com/wp-content/uploads/2021/01/SymmetricTree.png)
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:
- Both Left subtree and right subtree are empty or non-empty.
- Left Subtree is mirror image of right subtree, irrespective of data.
- 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:
- Check if two trees are mirror Trees of Each Other
- Convert Binary Tree to its Mirror Tree
- Introduction to Tree Data Structure
- Binary Tree Traversals
- Print All Leaf Nodes of a Binary Tree
- Count Number of Nodes in a Binary Tree
- Print Alternate Levels of Binary Tree
- Maximum Width of Binary Tree
- Level Order Tree Traversal
- Left View of Binary Tree
- Right View of Binary Tree
- Compute Height of Binary Tree
- Inorder Tree Traversal Using Stack
- Preorder Tree Trasversal Using Stack
- Postorder Tree Traversal Using Stack
- Vertical Order Tree Traversal
- Top View of Binary Tree
- Bottom View of Binary Tree
- Delete Complete Binary Tree
- Print All Root to Leaf Paths in a Binary Tree