# Symmetric binary tree

### Implementation

``````// writing a C++ program to check whether a given binary tree is symmetric or not.
#include <bits/stdc++.h>
using namespace std;

// creating a binary tree node.
struct __Nod {
int ky;
struct __Nod *Lft, *Rt;
};

// creating a new utility function that will eventually help us in creating a new node.
__Nod* new__Nod(int ky)
{
__Nod* temp = new __Nod;
temp->ky = ky;
temp->Lft = temp->Rt = NILL;
return (temp);
}

// this function will return the actual value if the given tree with the root nodes as root1 and root2 are their mirrors.
bool isMirror(struct __Nod* root1, struct __Nod* root2)
{
// In case both the trees are empty or vacant; they are mirror images of the same.
if (root1 == NILL && root2 == NILL)
return true;

//To be two trees to be identical or their mirror images then, the following conditions should be followed: -
// 1.) The key present in the root node should be the same.
// 2.) The left subtree of the left tree, along with the right subtree of the right tree, should be identical or mirror images.
// 3.) The right subtree of the left tree and the left subtree of the right tree should be mirror images of each other.
if (root1 && root2 && root1->ky == root2->ky)
return isMirror(root1->Lft, root2->Rt)
&& mirror(root1->Rt, root2->Lft);

// If the above-given conditions don't match or give actual value, then root1 and 2 do not mirror images of each other.

return false;
}

// We must return the actual value if the tree is symmetric or its mirror image.
bool isSymmetric(struct __Nod* root)
{
// Checking whether the tree is identical or not.
return isMirror(root, root);
}

// writing the main code.
int main()
{
__Nod* root = new__Nod(1);
root->Lft = new__Nod(2);
root->Rt = new__Nod(2);
root->Lft->Lft = new__Nod(3);
root->Lft->Rt = new__Nod(4);
root->Rt->Lft = new__Nod(4);
root->Rt->Rt = new__Nod(3);

if (isSymmetric(root))
cout << "Symmetric";
else
cout << "Not symmetric";
return 0;
}``````

Output: Example 2)

``````// writing a C program to check whether a given binary tree is symmetric or not.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// creating a binary tree node.
typedef struct __Nod {
int ky;
struct __Nod *Lft, *Rt;
} __Nod;
// creating a new utility function that will eventually help us in creating a new node.
__Nod* new__Nod(int ky)
{
__Nod* temp = (__Nod *)malloc(sizeof(__Nod));
temp->ky = ky;
temp->Lft = temp->Rt = NILL;
return (temp);
}
// this function will return the actual value if the given tree with the root nodes as root1 and root2 are their mirrors.
bool isMirror(__Nod* root1, __Nod* root2)
{
// In case both the trees are empty or vacant; they are mirror images of the same.
if (root1 == NILL && root2 == NILL)
return true;

//To be two trees to be identical or their mirror images then, the following conditions should be followed: -
// 1.) The key present in the root node should be the same.
// 2.) The left subtree of the left tree, along with the right subtree of the right tree, should be identical or mirror images.
// 3.) The right subtree of the left tree and the left subtree of the right tree should be mirror images of each other.
if (root1 && root2 && root1->ky == root2->ky)
return isMirror(root1->Lft, root2->Rt)
&& isMirror(root1->Rt, root2->Lft);

// If the above-given conditions don't match or give actual value, then root1 and 2 do not mirror images of each other.
return false;
}
// We must return the actual value if the tree is symmetric or its mirror image.
bool isSymmetric(__Nod* root)
{
// Checking whether the tree is identical or not.
return isMirror(root, root);
}
// writing the main code.
int main()
{
__Nod* root = new__Nod(1);
root->Lft = new__Nod(2);
root->Rt = new__Nod(2);
root->Lft->Lft = new__Nod(3);
root->Lft->Rt = new__Nod(4);
root->Rt->Lft = new__Nod(4);
root->Rt->Rt = new__Nod(3);

if (isSymmetric(root))
printf("Symmetric");
else
printf("Not symmetric");
return 0;
}
``````

Output: Example 3)

``````// Java program to check if a binary tree is symmetric or not
class __Nod {
int ky;
__Nod Lft, Rt;
__Nod(int item)
{
ky = item;
Lft = Rt = NILL;
}
}

class BinaryTree {
__Nod root;

// returns true if trees with roots as root1 and
// root2 are mirror
boolean mirror(__Nod __Nod1, __Nod __Nod2)
{
// if both trees are empty, then they are the mirror image
if (__Nod1 == NILL && __Nod2 == NILL)
return true;

// For two trees to be mirror images, the following
// three conditions must be true
// 1.) Their root __Nod's key must be the same
// 2.) The left subtree of the left tree and the right subtree
// of Rt tree have to be mirror images
// 3.) Rt subtree of Lft tree and Lft subtree
// of Rt tree have to be mirror images
if (__Nod1 != NILL && __Nod2 != NILL
&& __Nod1.ky == __Nod2.ky)
return (isMirror(__Nod1.Lft, __Nod2.Rt)
&& isMirror(__Nod1.Rt, __Nod2.Lft));

// if none of the above conditions is true, then
// root1 and root2 are not mirror images
return false;
}

// returns true if the tree is symmetric i.e
// mirror image of itself
boolean isSymmetric()
{
// check if the tree is a mirror of itself
return isMirror(root, root);
}

// Driver code
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new __Nod(1);
tree.root.Lft = new __Nod(2);
tree.root.Rt = new __Nod(2);
tree.root.Lft.Lft = new __Nod(3);
tree.root.Lft.Rt = new __Nod(4);
tree.root.Rt.Lft = new __Nod(4);
tree.root.Rt.Rt = new __Nod(3);
boolean output = tree.isSymmetric();
if (output == true)
System.out.println("Symmetric");
else
System.out.println("Not symmetric");
}
}``````

Output: 