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: