CareerCup

BTrees? Or Binary Trees? They are different...

Even if you meant Binary Trees, wtf is the question? Makes no sense.

bool check(node* r1, node* r2){
	if(!r1 && !r2) return true;
	if(!r1 || !r2) return false;
	if(r1->data != r2->data) return false;
	bool b = check(r1->left, r2->left) && check(r1->right, r2->right);
	if(b) return true;
	return check(r1->left, r2->right) && check(r1->right, r2->left);
}

bool isIsomorphic(tree t, tree s) 
{
	return  isSame(t,s) || isMirror(t,s);
}

There is nothing like left and right in a BTree. The number of branches from a node depend on the order of the tree.

Search for tree-isomorphism-problem in geekforgeeks . org.
I guess that is what you are looking for.

This question is from glassdoor where someone said it was asked in the on-site interview rounds. It is a very vague description.

The below answer is for lookup for a BT in a list of millions of BT.

We can do it in O(1) time, but it requires preprocessing.
1) Create a string hash for each tree
2) Remember to separate the node values using some separator. for example use left brace & right brace. Also remember to maintain the some sorted order of child's values (either asc, or desc)
3) Insert into a HashMap<String, Tree> map;


During lookup operation, convert the input tree into string (as mentioned in step 2), and look for it in the map.
Complexity:
HashMap addition is O(1) - Amortized.
HashMap lookup is O(1) - Amortized.

jbkjmb kj

a

gthg