## Friday, November 21, 2014

### 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