Foldable Binary Trees | GeeksforGeeks
Question: Given a binary tree, find out if the tree can be folded or not.
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
Method 2 (Check if Left and Right subtrees are Mirror)
Method 1 (Change Left subtree to its Mirror and compare it with Right subtree)
Write an Efficient C Function to Convert a Binary Tree into its Mirror Tree
Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.
http://prismoskills.appspot.com/lessons/Binary_Trees/Foldable_binary_tree.jsp
boolean isFoldable(Tree left, Tree right)
{
if (left == null && right == null)
return true;
if (left == null || right == null)
return false;
return
left.value == right.value &&
isFoldable(left.left, right.right) &&
isFoldable(left.right, right.left);
}
Read full article from Foldable Binary Trees | GeeksforGeeks
Question: Given a binary tree, find out if the tree can be folded or not.
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.
(a)
10
/ \
7 15
\ /
9 11
(b)
10
/ \
7 15
/ \
9 11
(c)
10
/ \
7 15
/ /
5 11
(d)
10
/ \
7 15
/ \ /
9 10 12
Method 2 (Check if Left and Right subtrees are Mirror)
bool IsFoldable(struct node *root){ if (root == NULL) { return true; } return IsFoldableUtil(root->left, root->right);}bool IsFoldableUtil(struct node *n1, struct node *n2){ /* If both left and right subtrees are NULL, then return true */ if (n1 == NULL && n2 == NULL) { return true; } /* If one of the trees is NULL and other is not, then return false */ if (n1 == NULL || n2 == NULL) { return false; } /* Otherwise check if left and right subtrees are mirrors of their counterparts */ return IsFoldableUtil(n1->left, n2->right) && IsFoldableUtil(n1->right, n2->left);}1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
mirror(root->left); /* See this post */
3) Check if the structure of left subtree and right subtree is same
and store the result.
res = isStructSame(root->left, root->right); /*isStructSame()
recursively compares structures of two subtrees and returns
true if structures are same */
4) Revert the changes made in step (2) to get the original tree.
mirror(root->left);
5) Return result res stored in step 2.
bool isFoldable(struct node *root){ bool res; /* base case */ if(root == NULL) return true; /* convert left subtree to its mirror */ mirror(root->left); /* Compare the structures of the right subtree and mirrored left subtree */ res = isStructSame(root->left, root->right); /* Get the originial tree back */ mirror(root->left); return res;}bool isStructSame(struct node *a, struct node *b){ if (a == NULL && b == NULL) { return true; } if ( a != NULL && b != NULL && isStructSame(a->left, b->left) && isStructSame(a->right, b->right) ) { return true; } return false;
}
/* UTILITY FUNCTIONS *//* Change a tree so that the roles of the left and right pointers are swapped at every node. See http://geeksforgeeks.org/?p=662 for details */void mirror(struct node* node){ if (node==NULL) return; else { struct node* temp; /* do the subtrees */ mirror(node->left); mirror(node->right); /* swap the pointers in this node */ temp = node->left; node->left = node->right; node->right = temp; }}Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.
(1) Call Mirror for left-subtree i.e., Mirror(left-subtree)
(2) Call Mirror for right-subtree i.e., Mirror(left-subtree)
(3) Swap left and right subtrees.
temp = left-subtree
left-subtree = right-subtree
right-subtree = temp
void mirror(struct node* node) { if (node==NULL) return; else { struct node* temp; /* do the subtrees */ mirror(node->left); mirror(node->right); /* swap the pointers in this node */ temp = node->left; node->left = node->right; node->right = temp; }} boolean isFoldable(Tree left, Tree right)
{
if (left == null && right == null)
return true;
if (left == null || right == null)
return false;
return
left.value == right.value &&
isFoldable(left.left, right.right) &&
isFoldable(left.right, right.left);
}
Read full article from Foldable Binary Trees | GeeksforGeeks
