Microsoft Interview Question
InternsTeam: idc
Country: India
Interview Type: Written Test
Hey Avinash, I am little confused at if condition where you checked if(n1->data < n2->data). shouldn't n2 be put back in q there and similarly n1 in p in next else if condition, then assign these to null? I feel, otherwise you will miss few comparisons. Please let me know if I am thinking wrong.
else
{
cout<<n1->data<<" ";
-------> p.pop();
-------> q.pop();
n1 = n1->right;
n2 = n2->right;
}
Above two lines pointed by arrow in code will give Empty Stack exception.
As you have already poped top items to n1 and n2 at the beginnning.
Correct me if i am wrong.
To Amit Singh: there is no exception:
1) Stacks are not empty since '!p.empty() && !q.empty()'.
2) Then the algo does 'if(...){pop()}else if(...){pop()}else{pop()}'. So the exception is not possible here.
Convert both trees to doubly linked list. O(n) space. And then find the intersection of these two linked lists. Much less space.
traverse first tree INORDER. Store it in an array ( this is ascending order). Now traverse the other tree and do binary search on the array...Alternatively you can also start traversing the other tree and search the first tree itself..no need to do the initial inorder traversal.
Hi,
So, the worst case efficiency would be (when both have no common elements),
let's say the number of element in the first BST is n
and the number of elements in the second BST is m
You check the first element in first BST and then do a binary search on the other.
O(nlogm), since you are doing binary search n times on a BST of m elements.
Is that correct?
I was thinking of a similar solution but somehow maintaining an array (with inorder traversal) seems to be efficient. It has a space overhead of O(m+n) but saves us tail recursion overhead.
Which would be great in larger BSTs
@BelligerentCoder: no need for searching the other tree. You can do it with just in-order traversal on both trees. Think of how the merge step works in mergesort. You can use a similar technique here.
@eugene: Yes, but if m is very large, for instance say n^100, then, a Theta(n log m) solution might fare better than a Theta(n+m) solution (assuming the trees are balanced).
@Anonymous: Very true. No need to go that far -- the example applies even for n^2 or technically for n^(1+e) for any e > 0, for that matter.
I suppose a full answer would specify this tradeoff, and further specify that if we do search the second tree, we should be iterating through the smaller tree and searching the larger tree.
In worst case, a tree might be aligned linearly (already sorted data). In that case, the complexity won't be nlogm. It will be (n * m). logn search complexity of a tree is an average case scenario.
Based on Johny's post:
void intersect(node* a, node* b) {
if (!a || !b) return;
if (a->value < b->value) {
intersect(a, b->left);
intersect(a->right, b);
}
else if (a->value > b->value) {
intersect(a->left, b);
intersect(a, b->right);
}
if (a->value == b->value) {
printf("%d ", a->value);
intersect(a->left, b->left);
intersect(a->right, b->right);
}
}
Recursive version. Time O(n) and Space O(n) where n > m
void findCommon(Node* r1, Node* r2) {
if (r1 == NULL || r2 == NULL) return;
if (r1->data == r2->data) {
cout << r1->data << "\n";
findCommon(r1->left, r2->left);
findCommon(r1->right, r2->right);
}
else if (r1->data < r2->data)
findCommon(r1, r2->left);
else
findCommon(r1->left, r2);
}
What is with the 'right' branches in 'else if' and 'else'? Seems the algo doesn't process them correctly.
If we know the sizes of the trees, say m and n where m<n. I will take the inorder traversal of the smaller tree (the tree with m nodes) then search for the elements in the second tree. It will take O(m ln n) time. It is similar to sourabh's answer. There are other ways but I cant think of more efficient way than this.
It can be sone in O(m+n) and O(m) space where m<=n
1. First find Inorder travelsal of smaller tree and store it in array. O(m).
2. Now Go through second tree inorder and start with the first element of array. If found print the element. If the element in array is less than the element on tree move to the next element of array.
- Do a BFS on the first tree and add the elements to an unordered_map
- Do a BFS on the second tree and check if those elements are present in the map [O(1) lookup]
- time/space =>O(m+n)/O(m) where m>=n
Flawless code ... Enjoy!!
InOrder traversing both the trees iteratively and checking for any common elements...
Time O(n) ... Space O(n) where n > m
- Avinash September 10, 2012