Google Interview Question Software Engineer / Developers
The question is "if same is defined as BSTs contain same sorted int array", so the interviewer didn't worry about shape. The question itself contains the the simples solution i.e do inorder traversal and compare the results, which would need O(m+n) additional space. I guess, he might ask a solution without using additional space.
1> If no of elements in both the trees are same, then try searching elements of on BST from other, if you don't find it its not same. O(nlogn) + 2n i.e nlogn
Mr Bean it would be O(2*n*logn) + O(2n) = O(2*n*logn) = O(n*logn)
Reason: If you only check if all the elements of BST-1 are present n BST-2 and not check if all the elements of BST-2 are also present in BST-1 then you might get wrong answers if BST-1 contains DUPLICATES but BST-2 doesn't contain any DUPLICATES!
The question is "if same is defined as BSTs contain same sorted int array", so the interviewer didn't worry about shape. The question itself contains the the simples solution i.e do inorder traversal and compare the results, which would need O(m+n) additional space. I guess, he might ask a solution without using additional space.
1> If no of elements in both the trees are same, then try searching elements of on BST from other, if you don't find it its not same. O(nlogn) + 2n i.e nlogn
Do you really save space? I think that in order for you to get the numbers from the first BST, you need to traverse it. What do you think?
Mr Bean it would be O(2*n*logn) + O(2n) = O(2*n*logn) = O(n*logn)
Reason: If you only check if all the elements of BST-1 are present n BST-2 and not check if all the elements of BST-2 are also present in BST-1 then you might get wrong answers if BST-1 contains DUPLICATES but BST-2 doesn't contain any DUPLICATES!
bool IsSimilar(tree* node1, tree* node2)
{
****if(!node1 && !node2)
********return true;
****if( (!node1&&node2) || (node1&&!node2) || (node1->value!=node2->value) )
********return false;
****return IsSimilar(node1->left,node2->left) && IsSimilar(node1->right,node2->right);
}
Please read the question.
"if same is defined as BSTs contain same sorted int array"
Your solution is the typical one for verifying if two trees have the same shape & data (same tree). Not the interviewer is asking for here.
Just do the same operation on the binarySearchTree at every step.. during Inorder.
bool FLAG;
inorder (node *root1,node *root2) {
if(root1 == NULL || root2 == NULL ){
if(FLAG)FLAG=false;
}
else if(root1->left =NULL && root1->right=NULL ) {
if(root1->data == root2->data) return;
else { if(FLAG)FLAG=false;
}
}
else {
inorder (root1->left,root2->left);
inorder (root1->right,root2->right);
}
}
Inorder is not sufficient to compare.
Need to check Inorder and Preorder traversals. If they are the same then BSTs are similar.
Only Comparing inorder traversal is not enough because it is Binary Search Tree ?
For example :
a) 20 b) 10
/ \ / \
10 40 5 20
/ \ \ / \
1 5 50 1 40
\
50
For above both three inorder will be 1, 5, 10, 20, 40, 50.
Why we need to check for Preorder traversals ?
Corrected example is as follows :
a) 20 b) 10
/ \ / \
10 40 5 20
/ \ \ / \
1 5 50 1 40
\
50
Sorry..my bad...didnot read the definition of 'is same' clearly.
Thanks for correcting :)
In the above example, a) and )b produce two different sequences by InOrder Tree Walk.
a)1 10 5 20 40 50
b)1 5 10 20 40 50
Your first tree is not even a BST. please check that. How can 5 come as the right child of 10 when 5 is less than 10.
How about taking level-wide travels on two trees? If finding not same nodes, return false; return true until finishing the traveling. Worst case is O(nlogn), average case would be less than O(nlogn)
how come O(nlogn), worst case is when you check all the elements which means it should O(n)
1. Flatten the trees to DLLs -O(log n)
- Mohan February 18, 20142. Loop through 'em - O(N)
3. Revert to trees. O(log n)
O(N) complexity game.