Check whether tree is Symmetric in C

Tree is Symmetric or Not?

Here, in this page we will discuss a C program to check whether a tree is Symmetric (mirror of itself) 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.

symmetric tree or not in C

Algorithm :

 

  • Create a recursive function isMirror() that takes two trees as an argument and returns 1 if trees are the mirrored and 0 if trees are not mirrored.
  • The isSMirror() function recursively checks two roots and subtrees under the root.
  • And isSymmetric() takes the root of the binary tree as an parameter and then will return true is isMirror() returns 1, otherwise it return 1.
  • If isSymmetric() returns 1 it means that given tree is symmetric, otherwise not  symmetric.
Symmetric tree or not

Code in C based on above approach

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

struct Node
{
int key;
struct Node* left;
struct Node* right;
};

struct Node* newNode(int data)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = data;
node->left = NULL;
node->right = NULL;

return(node);
}
int isMirror(struct Node* root1, struct Node* root2)
{

if (root1 == NULL && root2 == NULL)
return 1;

if (root1 && root2 && root1->key == root2->key)
return isMirror(root1->left, root2->right) && isMirror(root1->right, root2->left);

return 0;
}

int isSymmetric(struct Node* root)
{
return isMirror(root, root);
}

int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(4);
root->right->right = newNode(3);

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

Symmetric