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.


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”]


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;


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);

cout<<"Tree is foldable\n";
cout<<"Tree is not foldable\n";

return 0;