Foldable Binary Tree codein c++.

A Tree is said to be foldable if its left and right counter part can be made to overlap with each other .

For eg

 

Tree in Image 1 is foldable while Tree in Image 2 node is not.

Approach:-

First.
We can define a binary tree by mid-order and post-order or pre-order and mid-order, the mirror tree is same to the origin tree. So we can check these two trees’ mid-order and post-order are all same?

or we can use a recursive solution that check whether the two halves are mirror images of Each other or not.

[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 IsFoldableUtil(Treenode *node1, Treenode *node2)
{

if (!node1 && !node2 )
{ return true; }

if (!node1 || !node2)
{ return false; }

/* Otherwise check if lchild and rchild */
return IsFoldableUtil(node1->lchild, node2->rchild) &&
IsFoldableUtil(node1->rchild, node2->lchild);
}

// this dunction check for folding property in tree and return true in case of so
bool foldable(Treenode *A)
{
if (A == NULL)
{ return true; }

return IsFoldableUtil(A->lchild, A->rchild);
}

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(foldable(root))
cout<<"Tree is foldable\n";
else
cout<<"Tree is not foldable\n";

getchar();
return 0;
}

[/code]