Foldable Binary Trees - Given a binary tree, find out if the tree can be folded or not.

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  

1) If tree is empty, then return true.  
2) Convert the left subtree to its mirror image  
    mirror(root->left); /\* See [this](http://geeksforgeeks.org/?p=662) 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. 

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);  
}  

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;  
}