Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
@ran
i think to compare the values we need to store the value in some array (space required is 2N)........in BST ..........am i correct ????
and for binary trees hash the values of one tree and check for other
- We can keep a flag store/compare, so the space required is N
* for the first tree (flag is 'store') we can store the elements in an array
* for the second tree (flag is 'compare') we can just compare with the stored elements
- Yes, for Binary tree we can hash the values.
I am assuming two trees are same if all the nodes are same with same left/right childs.
Now start with root of both.
Compare roots IF equal, compare left and right and do this recursively.
boolean isSame(Node root1, Node root2){
if( (root1==null && root2!=null) || (root2==null && root1!=null))
return false;
if(root1 == null && root2 == null)
return true;
if(root1.data == root2.data)
return(isSame(root1.left,root2.left) && isSame( root1.right,root.right));
return false;
}
Combining one of Pre-Order & Post-Order Traversal, with In-Order traversal produces a unique tree.
In-order traversal of any BST with same elements will always return same sorted sequence of elements (does not matter what is the construction of tree)
So, with BST we need any one of Pre-Order & Post-Order traversal (In-Order traversal is implicitly those elements in sorted manner)
However, with a binary tree, we would need anyone of In-order & post-order traversal, and In-order traversal.
I agree with you. we cannot determine a tree structure unique only using inorder. we need to combine pre-order/ post-order with in-order to produce a unique tree.
In order to solve the problem we need to store inorder sequence in a array and then preorder/postorder in one more array. Then compare both these arrays against second tree.
time complexity would be O(n).
but space complexity would be O(2n).
If you're allowed extra space, couldn't you just add each node value of the first tree to a hash map? You can add it first with boolean value false, and then with the second tree, you can change them to true as you're traversing it. If you find an element that is not in the hash( or find that a number has been repeated) you can break and return false. If the tree traversal is completed, then you can check the hash to see if any of the values in the hash are still mapped to false. The time complexity should be O(n)...this should work if the given tree isn't a BST as well
[EDIT] Wouldn't track duplicates, but you can use count instead of boolean if thats the only issue. thoughts anyone?
bool IsStructureSame(node* root1,node* root2)
{
bool bIsSame = false;
if(root1 != nullptr && root2 != nullptr)
{
if(root1->data == root2->data)
{
if(IsStructureSame(root1->pLeft,root2->pLeft))
{
if(IsStructureSame(root1->pRight,root2->pRight))
bIsSame = true;
}
}
}
else if(root1 == nullptr && root2 == nullptr)
bIsSame = true;
return bIsSame;
}
for BST:
- Ran January 30, 2012- Do the inorder traversal on both the trees.
- This will yield sorted sequence
- compare the elements.