Given a node in binary tree - Check if left and right subtree are mirror of each other

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 

• http://stackoverflow.com/questions/8436623/check-if-a-binary-tree-is-a-mirror-image-or-symmetric