Check if Binary Tree is Foldable Tree

Question:

Given a binary tree root node, check if the tree is a foldable tree.

Example:
Consider the image given below

We can see that, the nodes of left and right Subtree are exact mirror of each other.

So we can solve this problem by using “Check if Two Trees are Mirror Structure to each other” approach.

The only difference here is, we will be checking on only 1 tree.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};



bool check_if_mirror_structure(Node *node1, Node *node2) 
{
    if (node1 == NULL && node2 == NULL) 
    {
      return true;
    }

    if (node1 == NULL || node2 == NULL) 
    {
      return false;
    }

    return check_if_mirror_structure(node1->left, node2->right) && check_if_mirror_structure(node1->right, node2->left);
}



bool check_if_foldable_tree(Node *node) 
{
    if (node == NULL) 
    {
      return true;
    }

    return check_if_mirror_structure(node->left, node->right);
}


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    if(check_if_foldable_tree(root))
    {
        cout<<"Tree is a foldable tree"<<endl;
    } else {
        cout<<"Tree is Not a foldable tree"<<endl;
    }

    return 0;  
}  

Output:

Tree is a foldable tree