Introduction
If the left and right subtrees of a binary tree are mirror images of each other, the tree can be folded. An empty tree can also be folded. Because both binary trees have a left subtree that is the mirror image of the right subtree, they can be folded.
Approaches
-
Change the left subtree to its mirrored counterpart. After that, see if the mirror is the same as the right subtree.
- Check to see if the right and left subtrees are mirror images of each other.
Approach 1
-
If the tree is empty, return true.
-
Create a mirror replica of the left subtree.
-
Return true if the right subtree is equivalent to the mirror image; otherwise, return false.
void Check(node* Node)
{
if ( Node == NULL )
return;
else {
node* temp;
Check( Node–>left );
Check( Node–>right );
temp = Node–>left;
Node–>left = Node–>right;
Node–>right = temp;
}
}
Approach 2
In the check(a,b) function:
-
If both trees are empty, true is returned.
-
Return false if only one of them is empty.
-
Return true if one subtree is a mirror of another.
bool Check(node* x1, node* x2)
{
if (x1 == NULL && x2 == NULL) {
return true;
}
if (x1 == NULL || x2 == NULL) {
return false;
}
return Check(x1–>left, x2–>right)
&& Check(x1–>right, x2–>left);
}
foldable(a) function:
-
We'll verify if the trees are null first, then return true if they are.
-
Otherwise, use the check function to see if the left and right subtrees are mirror images of each other.
bool dofoldable(node* root)
{
if (root == NULL) {
return true;
}
return Check(root–>left, root–>right);
}
Must Recommended Topic, Binary Tree Postorder Traversal.