Saturday, January 18, 2014

Given a binary tree find out whether the left and right sub-trees are mirror images of each other

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createnode(int x)
{
struct node* new_node=(struct node*)malloc(sizeof(struct node*));
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
}

int isMirror(struct node* node1, struct node* node2)
{
if(node1 == NULL && node2 != NULL)
{
return 0;
}
else if(node1 != NULL && node2 == NULL)
{
return 0;
}
else if(node1 == NULL && node2 == NULL)
{
return 1;
}
else if(node1->data != node2->data)
{
return 0;
}
return isMirror(node1->left, node2->right) && isMirror(node1->right, node2->left);
}


int height(struct node* root)
{
if(root==NULL)
{
return 0;
}
else
{
int lheight=1+height(root->left);
int rheight=1+height(root->right);
return lheight>rheight?lheight:rheight;
}
}

void levelorderprint(struct node* root,int level)
{
if(root && level==0)
{
printf("%d ",root->data);
}
else if(root)
{
levelorderprint(root->left,level-1);
levelorderprint(root->right,level-1);
}
}

void levelorder(struct node* root)
{
int h=height(root);
for(int i=0;i<h;i++)
{
levelorderprint(root,i);
printf("\n");
}
}

int main()
{
struct node* root1=createnode(1);
root1->left=createnode(2);
root1->right=createnode(2);
root1->left->right=createnode(4);
root1->left->left=createnode(3);
root1->right->right=createnode(3);
root1->right->left=createnode(4);
//root1->right->right->left=createnode(8);
printf("The input tree is:\n");
levelorder(root1);
int result = 0;
result = isMirror(root1, root1);
if(result == 1)
{
printf("The left and right subtrees are mirror images\n");
}
else
{
printf("The left and right subtrees are not mirror images\n");
}
return 0;
}

No comments:

Post a Comment