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
1
/ \
2 2
/ \ / \
4 3 3 4
1
/ \
2 2
/ \ / \
3 4 3 4
1
/ \
2 2
/ \
3 3
### 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 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 **
* [http://stackoverflow.com/questions/8436623/check-if-a-binary-tree-is-a-mirror-image-or-symmetric](http://stackoverflow.com/questions/8436623/check-if-a-binary-tree-is-a-mirror-image-or-symmetric)