Problem
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.
Examples
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
Solution
Method 1 (Change Left subtree to its Mirror and compare it with Right subtree)
Algorithm: isFoldable(root)
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.
Method 2 - Using recursion
here is the pseudocode:
boolean mirrorEquals(BTree left, BTree right) {
if (left == null || right == null)
return left == null && right == null;
return left.value == right.value && mirrorEquals(left.left, right.right) && mirrorEquals(left.right, right.left);
}
Method 3 - Iteratively
bool isMirrorItselfIteratively(BinaryTreeNode *root)
{
/// use single queue
if(!root) return true;
queue<BinaryTreeNode> q;
q.push(root.left);
q.push(root.right);
BinaryTreeNode l, r;
while(!q.empty()) {
l = q.front();
q.pop();
r = q.front();
q.pop();
if(l==NULL && r==NULL) continue;
if(l==NULL || r==NULL || l.data!=r.data) return false;
q.push(l.left);
q.push(r.right);
q.push(l.right);
q.push(r.left);
}
return true;
}
Thanks.
References