Check whether two trees are symmetrical or not.

We need to write a recursive function isSymmetrical() that takes two trees as argument and returns true if trees are Symmetrical and false if trees are not Symmetrical. The isSymmetrical() function recursively checks two roots and subtrees under the root.

The code for above js as follows:

[code language=”cpp”]

#include<bits/stdc++.h>

struct Treenode// definition of structure of tree node which has lchild child and rchild child
{
int val;
Treenode* lchild;
Treenode* rchild;
};

struct Treenode* newNode(int key)// function for new node creation
{
struct Treenode* newnode = (struct Treenode*)malloc(sizeof(struct Treenode));
newnode->val = key;
newnode->lchild = NULL;
newnode->rchild = NULL;

return(newnode);
}

bool isMirror(Treenode *root1, Treenode *root2)
{
// If both trees are empty, then they are mirror images
if (!root1 && !root2)
return true;

// For two trees to be mirror images, the following three
// conditions must be true
// 1 – Their root node’s key must be same
// 2 – lchild subtree of lchild tree and rchild subtree
// of rchild tree have to be mirror images
// 3 – rchild subtree of lchild tree and lchild subtree
// of rchild tree have to be mirror images
if (root1 && root2 && root1->val == root2->val)
return isMirror(root1->lchild, root2->rchild) &&
isMirror(root1->rchild, root2->lchild);

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

// Returns true if a tree is symmetric i.e. mirror image of itself
bool isSymmetric(Treenode* root)
{
// Check if tre is mirror of itself
return isMirror(root, root);
}

int main()
{
Treenode *root1 = newNode(232);
Treenode *root2 = newNode(232);// these part is concerned with creation of tree
// user can edit this as per wish
root1->lchild = newNode(231);
root1->rchild = newNode(231);
root1->lchild->lchild = newNode(431);
root1->lchild->rchild = newNode(531);

root2->lchild = newNode(231);
root2->rchild = newNode(331);
root2->lchild->lchild = newNode(431);
root2->lchild->rchild = newNode(513);

if(isSymmetric(root))
cout<<"Tree is symmetric\n";
else
cout<<"Tree is not symmetric\n";

getchar();
return 0;
}

[/code]