Saturday, October 18, 2014

Problem

A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.

Example

``````  1
/ \
2   2
``````
TRUE
``````   1
/ \
2   2
\
3
``````
FALSE
``````     1
/   \
2     2
/ \   / \
4   3 3   4
``````
TRUE
``````       1
/   \
2     2
/ \   / \
3   4 3   4
``````
FALSE
``````       1
/   \
2     2
/       \
3         3
``````
TRUE

Solution

Method 1 - Recursiion mirrorEquals(BTree left , BTree right)
Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.
```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 2 - Iterative solution using queue
Insert 2 elements at a time and then pop and compare the values, and continue to do with the children.

```bool isMirrorItselfIteratively(BTree root)
{
/// use single queue and initial push
if(!root) return true;
queue<btree> q;
q.push(root.left);
q.push(root.right);

BTree 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 ) return false;
if(l.data!=r.data) return false;
//not the push ordering
q.push(l.left);
q.push(r.right);
q.push(l.right);
q.push(r.left);
}

return true;
}
```

References