CareerCup

public boolean areEqual(Node node1, Node node2) {
    if (node1 == null && node2 == null) {
		return true;
	} 
	if (node1 == null || node2 == null || node1.value != node2.value) {
		return false;
	}
	 
	if ((areEqual(node1.left, node2.left) && areEqual(node1.right, node2.right)) ||  (areEqual(node1.left, node2.right) && areEqual(node1.right, node2.left))) {
		return true;
	}	 
	return false;
 }

/* Given two trees, return true if they are
 structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
    /*1. both empty */
    if (a==NULL && b==NULL)
        return 1;
 
    /* 2. both non-empty -> compare them */
    if (a!=NULL && b!=NULL)
    {
        return
        (
            a->data == b->data &&
            identicalTrees(a->left, b->left) &&
            identicalTrees(a->right, b->right)
        );
    }
     
    /* 3. one empty, one not -> false */
    return 0;
}

bool compare(TreeNode* a, TreeNode* b)
{ 
    if (a == NULL && b == NULL) return true;
    else if (a == NULL ^ b == NULL) return false;
    bool noswap = compare(a->left, b->left) && compare(a->right, b->right);
    bool swap = compare(a->left, b->right) && compare(a->right, b->left);
    return a->val == b->val && (swap | noswap); 
}

This problem, also referred as Tree Isomorphism can be implemented recursively. The approach is to implement the code that detects if two trees are identical and add component that considers thatc branches have been swapped. Below is C/C++ code

bool isomorphic(node *n1, node *n2)
{
	if (n1==NULL && n2==NULL) return true;
	if (n1==NULL || n2==NULL) return false;
	if (n1->val != n2->val) return false;
			 //have not been swapped
	return (isomorphic(n1->left, n2->left) && isomorphic(n1->right && n2->right) ||
			isomorphic(n1->left, n2->right) && isomorphic(n1->right, n2->left));
			//have been swapped
}

Your solutions work in O(2 ^ n) time, add memorization to make complexity O(n ^ 2)