WAP to Check Given Binary Tree Can Have Mirror Image e.g we have to Check wheather This Tree Can Be Foldable or Not

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Consider the below trees:
(a) can be folded.
(d) cannot be folded.


a)
10
/ \
7 15
\ /
9 11


(c)
b
/ \
f e
/ /
a q

(d)

a
/ \
b c
/ \ /
e f d


Algorithm

IsFold(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
each other. Use utility function IsFoldable(root->left,
root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldable(n1, n2)
1) If both trees are empty then return true.
2) If one of them is empty and other is not then return false.
3) Return true if following conditions are met
a) n1->left is mirror of n2->right
b) n1->right is mirror of n2->left


#include
#include

/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
#define bool int
#define true 1
#define false 0

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* A utility function that checks if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldable(struct node *n1, struct node *n2);

/* Returns true if the given tree can be folded */
bool IsFold(struct node *root)
{
if (root == NULL)
{ return true; }

return IsFoldable(root->left, root->right);
}

/* A utility function that checks if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldable(struct node *n1, struct node *n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == NULL && n2 == NULL)
{ return true; }

/* If one of the trees is NULL and other is not,
then return false */
if (n1 == NULL || n2 == NULL)
{ return false; }

/* Otherwise check if left and right subtrees are mirrors of
their counterparts */
return IsFoldable(n1->left, n2->right) &&
IsFoldable(n1->right, n2->left);
}

/*UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test mirror() */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);

if(IsFold(root) == true)
{ printf("\n tree is foldable"); }
else
{ printf("\n tree is not foldable"); }

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/7J0hM