In this tutorial, we are going to explore the concept of a collapsible binary tree in C++. Within the C++ programming language, a collapsible binary tree represents a tree-based data structure where each node possesses mirror-image left and right subtrees. To qualify as collapsible, the structure of the left and right subtrees must align perfectly when the tree is folded along its central axis. This symmetrical arrangement is verified sequentially during the implementation of a collapsible binary tree. The collapsibility of the tree is confirmed when the left and right children of every node coincide. To achieve this property, recursive techniques can be employed in C++, which are fundamental for various tree-related operations.
We can use different kinds of Approaches:
- Foldable Binary Trees by Switching to the Mirror of the Left Subtree
- Foldable Binary Trees can be found by determining whether the left and right subtrees are mirror images:
- By using the Breadth-First-Search Approach
1. Foldable Binary Trees by Switching to the Mirror of the Left Subtree
The objective is to transform the left subtree into its mirror and then compare it to its right subtree . You can follow these steps to solve the problem:
- If the tree is empty, return true.
- Next, transform the left subtree to its mirror image.
- After that, check and save the result if the structure of both subtrees on the left and right is the same.
- istheStructSame(root->left, root->right) = res. istheStructSame recursively compares structures in two subtrees and returns true if the structures are the same.
- Undo the changes done in step (2) to get back the original tree.
- Finally, return the result res that was stored in step 3.
Filename: Is_foldable.cpp
Example
//A C++ program to determine if a binary tree is foldable.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree in which each node has data, a pointer to the left child, and a pointer to the right child */
class node {
public:
int value;
node* left;
node* right;
};
// converts the given binary tree to a mirror image
void mirror_image(node* node);
// returns true if both trees are the same
bool istheStructSame(node* a1, node* b1);
/* function to determine if the tree is foldable or not*/
bool is_Foldable(node* root)
{
bool result;
//base condition
if (root == NULL)
return true;
// left subtree is converted to a mirror image
mirror_image(root->left);
/* Comparing the structures of the right and left subtrees */
result = istheStructSame(root->left, root->right);
// to revert to the original tree
mirror_image(root->left);
return result;
}
bool istheStructSame(node* a1, node* b1)
{
if (a1 == NULL && b1 == NULL) {
return true;
}
if (a1 != NULL && b1 != NULL
&& istheStructSame(a1->left, b1->left)
&& istheStructSame(a1->right, b1->right)) {
return true;
}
return false;
}
/* Modify a tree so that the left and righcpp tutorialer roles are switched at each node.*/
void mirror_image(node* Node)
{
if (Node == NULL)
return;
else {
node* t;
mirror_image(Node->left);
mirror_image(Node->right);
// pointer swapping
t = Node->left;
Node->left = Node->right;
Node->right = t;
}
}
/* Assists allocating a new node with the specified data and NULL right and left references. */
node* newNode(int value)
{
node* Node = new node();
Node->value = value;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
//main selection
int main(void)
{
/* the structure of the binary tree
1
/ \
9 7
\ /
6 8
*/
node* root = newNode(1);
root->left = newNode(9);
root->right = newNode(6);
root->left->right = newNode(7);
root->right->left = newNode(8);
if (is_Foldable(root) == 1) {
cout << "The given tree is foldable. ";
}
else {
cout << "\nThe given tree is not foldable. ";
}
return 0;
}
Output:
Output
The given tree is foldable.
2. Foldable Binary Trees can be found by determining whether the left and right subtrees are mirror images:
The objective is to determine whether the left and right subtrees are mirrors. You can follow these steps to solve the problem:
- If the tree is empty, return true.
- Otherwise, check if the left and right subtrees are structurally similar. Use the utility function IsFoldable(root->left, root->right) .
- Check whether m1 and m2 are mirror images of one other.
- If neither tree is empty, return true.
- If one is empty while the other one is not, return false .
- If the following requirements are met, return true.
- n1->left is a mirror image of n2->right .
- n1->right is a mirror image of n2->left .
Filename: Isfoldablemirror.cpp
Example
#include <bits/stdc++.h>
using namespace std;
/* A binary tree in which each node has data, a pointer to the left child, and a pointer to the right child */
class node {
public:
int value;
node* left;
node* right;
};
// returns true if both trees are the same
bool IsFoldabletree(node* n1, node* n2);
/* Returns true if the given tree can be folded */
bool Is_Foldable(node* root)
{
if (root == NULL) {
return true;
}
return IsFoldabletree(root->left, root->right);
}
/* A function that determines whether trees with roots m1 and m2 are mirror images of one other */
bool IsFoldabletree(node* m1, node* m2)
{
/* if both left and right subtrees are null, then return tree*/
if (m1 == NULL && m2 == NULL) {
return true;
}
//If either of the trees is null, then return false
if (m1 == NULL || m2 == NULL) {
return false;
}
/*If not, verify if the left and right subtrees are mirror images of each other */
return IsFoldabletree(m1->left, m2->right)
&& IsFoldabletree(m1->right, m2->left);
}
/* Assists allocating a new node with the specified data and NULL right and left references. */
node* newNode(int value)
{
node* Node = new node();
Node->value = value;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
int main(void)
{
/* The structure of the binary tree
1
/ \
6 7
\ /
8 9
*/
node* root = newNode(1);
root->left = newNode(6);
root->right = newNode(7);
root->left->right = newNode(8);
root->right->left = newNode(9);
if (Is_Foldable(root) == true) {
cout << "The given tree is foldable.";
}
else {
cout << "The given tree is not foldable.";
}
return 0;
}
Output:
Output
The given tree is foldable.
3. By using the Breadth-First-Search Approach
Traversing the tree is accomplished by employing a Queue and the Breadth-First Search (BFS) method. To resolve the issue, adhere to these guidelines:
- The right child of the right subtree corresponds to the left child of the left subtree, ensuring their validity.
- The left child of the right subtree must match the right child of the left subtree, with both being either null or non-null.
Filename: IsFoldableTree.cpp
Example
#include <bits/stdc++.h>
using namespace std;
// Class Node for storing data as well as left and right
// pointers
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
class IsFoldableTrees
{
public:
Node *root = NULL;
// function to find whether the tree is foldable or not
bool isFoldableTree()
{
// for storing nodes
queue<Node *> q1;
//Adding the left and right nodes to the queue
if (root != NULL)
{
q1.push(root->left);
q1.push(root->right);
}
while (!q1.empty())
{
// Remove the first two nodes.
// Check for a null conditions.
Node *p1 = q1.front();
q1.pop();
Node *r1 = q1.front();
q1.pop();
// If both are null, continue and examine the subsequent elements
if (p1 == NULL && r1 == NULL)
continue;
//If either of them is null return false
if ((p1 == NULL && r1 != NULL) || (p1 != NULL && r1 == NULL))
return false;
/* Insert in the following order: 1. left of left subtree
2. the right of the right subtree
3.to the right of the left subtree
4.left subtree of the right */
q1.push(p1->left);
q1.push(r1->right);
q1.push(p1->right);
q1.push(r1->left);
}
//If tree is foldable
return true;
}
};
int main()
{
IsFoldableTrees tr = IsFoldableTrees();
//Inserting data into the tree
tr.root = new Node(1);
tr.root->left = new Node(9);
tr.root->right = new Node(10);
tr.root->right->left = new Node(23);
tr.root->left->right = new Node(45);
// function calling
if (tr.isFoldableTree())
cout << "The given tree is foldable" << endl;
else
cout << "The given tree is not foldable" << endl;
}
Output:
Output
The given tree is foldable.
