CareerCup

calling------------------ isFoldable(root.getLeft(),root.getRight()));

private static BinaryTreeNode createBinaryTreeFoldable() {
		// TODO Auto-generated method stub
		BinaryTreeNode node1 = new BinaryTreeNode(10);
		BinaryTreeNode node2 = new BinaryTreeNode(20);
		BinaryTreeNode node3 = new BinaryTreeNode(20);
		BinaryTreeNode node4 = new BinaryTreeNode(30);
		BinaryTreeNode node5 = new BinaryTreeNode(40);
		BinaryTreeNode node6 = new BinaryTreeNode(40);
		BinaryTreeNode node7 = new BinaryTreeNode(30);

		node1.setLeft(node2);
		node1.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);
		node3.setRight(node7);
		return node1;
	}


private static boolean isFoldable(BinaryTreeNode root1, BinaryTreeNode root2) {
		if (root1 == null && root2 == null)
			return true;
		if ((root1 == null && root2 != null)
				|| (root1 != null && root2 == null))
			return false;

		if (root1.getData() != root2.getData())
			return false;
		else
			return isFoldable(root1.getLeft(), root2.getRight())
					&& isFoldable(root1.getRight(), root2.getLeft());
	}

Recursive approach:

private static boolean isFoldable(BinaryTree t1, BinaryTree t2) {
	
		if (t1 == null && t2 == null)
			return true;

		if (t1 == null || t2 == null)
			return false;

		if (t1.getData() != t2.getData())
			return false;

		return isFoldable(t1.getLeft(), t2.getRight()) && isFoldable(t1.getRight(), t2.getLeft());
	}

Following is a non-recursive approach :

#define TRUE 1
#define FALSE 0

int isFoldable(Node * head){
	char [] leftSequence = left_to_right_preorder(head->left_child);
	char [] rightSequence = right_to_left_preorder(head->right_child);
	
	if(is_equal(leftSequence, rightSequence)){
		return TRUE;		
	}
	return FALSE;
}

char[] left_to_right_preorder(Node * node){
	Queue queue;
	enqueue_left_to_right_in_queue(&queue, node);	
	char result[queue.size() + 1];
	result[0] = queue.size();
	for(int i = 1;i <= queue.size(); i++){
		result[i] = queue.pop().value;
	}
	return result;
}

void enqueue_left_to_right_in_queue(Queue * queue, Node * node){
	if(node != null){
		queue.push(node);
		enqueue_left_to_right_in_queue(queue, node->left);
		enqueue_left_to_right_in_queue(queue, node->right);
	}	
}

char[] right_to_left_preorder(Node * node){
	Queue queue;
	enqueue_right_to_left_in_queue(&queue, node);
	
	char result[queue.size()+ 1] ;
	result[0] = queue.size();
	
	for(int i = 1 ; i <= queue.size(); i++){
		result[i] = queue.pop().value;
	}
	return result;
}

void enqueue_right_to_left_in_queue(Queue * queue, Node * node){
	if(node != null){
		queue.push(queue, node);
		enqueue_right_to_left_in_queue(queue, node->right_child);
		enqueue_right_to_left_in_queue(queue, node->left_child);
	}
}

int is_equal(char* first, char* second){
	if(first[0] != second[0]){
		return 0;
	}
	for(int i = 1; i <= first[0]; i++){
		if(first[i] != second[i]){
			return 0;
		}
	}
	return 1;
}

How about this:

1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree). 
3. Pop R.
4. Now we would go to right sub tree of R. 
5. Process an element E in in-order traversal, 
6. POP from stack1.
    if (stack empty)
       return false
    else if (popped element = E) 
       goto 5.
    else
       return false;
7. if (stack empty)
       return true;
    else
       return false;

How about this:

1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree). 
3. Pop R.
4. Now we would go to right sub tree of R. 
5. Process an element E in in-order traversal, 
6. POP from stack1.
    if (stack empty)
       return false
    else if (popped element = E) 
       goto 5.
    else
       return false;
7. if (stack empty)
       return true;
    else
       return false;

How about this:

1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree). 
3. Pop R.
4. Now we would go to right sub tree of R. 
5. Process an element E in in-order traversal, 
6. POP from stack1.
    if (stack empty)
       return false
    else if (popped element = E) 
       goto 5.
    else
       return false;
7. if (stack empty)
       return true;
    else
       return false;

How come the answer is true in the given example? The toot has 2 children - 3 and 2. The tree is nonfoldablr because the root of the child subtrees is not same. Right? Or am I missing something?

Define a Method IsMirror(Tree t1, Tree t2);
Now problem is just to call this method appropriately

bool IsFoldable(Tree t)
{
  if (t == null) return true;
  return IsMirror(t.Left, t.Right);
}

bool IsMirror(Tree t1, Tree t2)
{
   if (t1 == null && t2 == null)
  {
     return true;
   }

   if (t1 == null || t2 == null)
   {
     return false;
   }
  if (t.data != t2.data)
 {
   return false;
 }
 return IsMirror(t1.right, t2.left) && (t1.left. t2.right);
}

non-recursive way

bool isMirrorTree (treeNode * root)
{
     std::queue<treeNode *> treeQ;
     bool isMirror = true;

     if (root->l == NULL && root->r ==NULL)
	     return true;

     if ((root->l == NULL && root->r !=NULL) ||
		     (root->l != NULL && root->r == NULL))
	     return false;

     treeQ.push (root->l);
     treeQ.push (root->r);

     while (! treeQ.empty()) {
	     treeNode *first = treeQ.front ();
	     treeQ.pop ();
	     treeNode *second= treeQ.front ();
	     treeQ.pop ();

	     if ( first && second && first->x == second->x)
	     {
		     treeQ.push (first->l);
		     treeQ.push (second->r);
		     treeQ.push (first->r);
		     treeQ.push (second->l);
	     }
	     else
	     {
		     if (! (first == NULL && second == NULL))
		         isMirror =false;
		     break;
	     }
     }
     return isMirror;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isMirror(TreeNode* root) {
        if(root->right->val==root->left->val)
        {
            return isEqual(root->left->left,root->right->right)&&isEqual(root->left->right,root->right->left);
            
        }
        else return false;
    }
    bool isEqual(TreeNode* root1,TreeNode* root2) {
        if(root1->val==root2->val)
        {
            return isEqual(root1->left,root2->left)&&isEqual(root1->right,root2->right);
            
        }
        else return false;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isMirror(TreeNode* root) {
        if(root->right->val==root->left->val)
        {
            return isEqual(root->left->left,root->right->right)&&isEqual(root->left->right,root->right->left);
            
        }
        else return false;
    }
    bool isEqual(TreeNode* root1,TreeNode* root2) {
        if(root1->val==root2->val)
        {
            return isEqual(root1->left,root2->left)&&isEqual(root1->right,root2->right);
            
        }
        else return false;
    }
};