Amazon Interview Question Software Engineer / Developers
If I understood it correctly, simply make an inroder traversal of the tree1 and with every node traversed, keep adding it to tree2 and then free the node. The insert method on tree2 should take care of duplicates while adding the nodes. Its pretty simple, unless balancing is required as a follow-on question. in that case, instead of inorder traversal, a breadth first traversal should do the job.
You are right, but it can even be done better, an O(n) solution
using extra space and also an O(n) in place solution also exits,
try for that.
Using a recursion, they can be merged to the extent of maintaining the complete balance in the merged tree.
The routine returns the root node of the merge trees LNode and RNode
BST_MERGE(LNode,RNode){
//bottom out condition
If(LNode==Null) return RNode;
elseif (RNode==Null) return LNode;
}
//recursion
if(LNode.data>=RNode.data){
LNode.left=BST_MERGE(LNode.left,RNode);
return LNode;
}
else{
RNode.left=BST_MERGE(RNode.left,LNode);
return RNode;
}
It's hard for me to verify if this is correct or not. But it does not seem right ...
For starters, I am a bit puzzled by the fact that you're checking only left children? Also, is the beginning of your recursion BST_MERGE(root1, root2)? If so, imagine 2 trees, each really a linked list with only right children. Then the recursion will end almost immediately and the resulting tree will be BST if and only if all elements of one tree are <= all elements in the other tree.
Example:
Tree1: Tree2: Merged tree:
1 2 2
3 4 1 4
5 6 3 6
5
Clearly not a BST :-(
How about using In-order traversal to make two sorted arrays and then perform a two way merging? From the final merged sorted array, rebuild a balanced BST?
<pre lang="c++" line="1" title="CodeMonkey87449" class="run-this">void merge (node *tree1, node *tree2) {
if (tree2->val <= tree1->val) {
node *right_child = tree2->right;
tree2->right = NULL;
if (!tree1->left) {
tree1->left = tree2;
} else {
merge(tree1->left, tree2);
}
if (right_child)
merge(tree1, right_child);
} else {
node *left_child = tree2->left;
tree2->left = NULL;
if (!tree1->right) {
tree1->right = tree2;
} else {
merge(tree1->right, tree2);
}
if (left_child)
merge(tree1, left_child);
}
}
</pre><pre title="CodeMonkey87449" input="yes">
</pre>
private Node merge (Node head1, Node head2)
{
if (head1 == null) return head2;
if (head2 == null) return head1;
if (head1.data > head2.data)
{
Node temp = head2.right;
head2.right = null;
head1.left = merge (head1.left, head2);
head1 = merge (head1, temp);
return head1;
}
else if (head1.data < head2.data)
{
Node temp = head2.left;
head2.left = null;
head1.right = merge (head1.right, head2);
head1 = merge (head1, temp);
return head1;
}
else
{
head1.left = merge (head1.left, head2.left);
head1.right = merge (head1.right, head2.right);
return head1;
}
}
Any restriction? This can be as simple as picking up a leaf node from one of the trees and compare the value of this leaf node to that of the two root nodes. The new root is the node with median value.
- Anonymous September 24, 2010