Amazon Interview Question Software Engineer / Developers
Country: United States
there's a way to do O(1) space tree traversal, which is called Morris Traversal. the idea is to add additional right link to a right leaf node's successor
Here goes the logic:
1. Find first element in tree T1 as well as T2 while doing an inorder search (this is equivalent to finding smallest element in the tree.
- This can be starting from root, if left child is not null, leftmost child is the least node
- If no left child for root, root itself
2. Compare the two values, if not same return false else
3. Call inorder successor on both trees and find next smallest element
4. GO to step 2
5. If both the trees are exhausted (be careful here), return true else false (one is subset of other)
Don't know what GC_PENNY is dreaming, but the "best" solution if parent pointers are not available seems to be (to me):
2 stacks, one for each tree.
Iteratively in order traverse each tree using independent stacks but check intermittently after each iteration in the obvious way for equality (and break if a no math condition is detected).
Stacks aren't O(1) space, so this doesn't work. it would work if there was no space limit, but doesn't work given the constraints of the question.
The Inorder of BSTs will be equal if both trees contain same elements .
We can check if two BSTs contains same elements by XORing all the elements in the tree with the other .
public boolean isBSTEqual(BinaryTree *root1,BinaryTree *root2){
int xorOfBST1=getXOROFTree(root1);
int xorOfBST2=getXOROFTree(root2);
return xorOfBST1==xorOfBST2 ? true : false;
}
public int getXOROFTree(BinaryTree *root){
if(root==null) return 0;
return getXOROFTree(root->left) ^ getXOROFTree(root->right) ^ root->data;
}
void isSame(node* root1, node* root2, bool& isSame)
{
if( root1==NULL && root2 ==NULL) {
isSame = true;
return;
}
if( (root1 == NULL && root2 != NULL) || (root1!=NULL && root2!=NULL) {
isSame = false;
return;
}
isSame(root1->left, root2->left, isSame);
if( root1->data != root2->data){
isSame = false;
return;
}
isSame( root1->right, root2->right, isSame);
}
It's not correct answer. You are assuming that the threes have the same structure whereas the threes can have different structure and the same in order traversal.
E.g
3
/ \
2 4
and
2
\
3
\
4
I got it, thank you :). So, in this situation we should rebuild one of the threes to make roots the same and then use the code above.
public bool compareInOrder (Node root1, Node root2) {
Node node1 = getInOrderNext (root1.left, root1);
Node node2 = getInOrderNext (root2.left, root2);
while ( node1 && node2) {
if ( !node1.equals(node2) )
return false;
else {
node1 = getInOrderNext (node1, null);
node2 = getInOrderNext (node2, null);
}
}
if ( node1 || node2)
return false;
return true;
}
//the key thing is storing reference to parent in current.right, so you can go backward
public Node getInOrderNext (Node current, Node parent) {
Node ret_value = null;
while(current != null && ret_value == null) {
if (parent != null) {
parent.left = current.right;
current.right = parent;
}
if (current.left != null) {
parent = current;
current = current.left;
} else {
ret_value = current;
current = current.right;
parent = null;
}
}
return ret_value;
}
1, find the minimum of each binary search tree
- Anonymous February 24, 20142. call successor for each binary search tree