Walmart Labs Interview Question
Developer Program EngineersCountry: India
Interview Type: Phone Interview
STEP 1
CONVERT BOTH TREES IN DOUBLY LINKED LIST O(n)
Step 2
Merge these linked list O(n)
Step 3
Again create back the tree O(n)
Well what is the point in converting them specifically to DOUBLY LL's . We can do the same thing for SINGLY LL's.
I think since a Tree node is similar to a DLL node it is good to make a DLL. A BST can be converted to a DLL using recursion( Google The great tree list recursion problem). once you have a DLL its lchild * will point to previous node and rchild * will point to next node. This property will remain same even after merging.
Furthur to convert a BST To tree in O(n) is a little tricky algo. But it you think of it as inorder tree creation it becomes easy.
list *head;//global
tree * createBSTfromDLL(int num_nodes)
{
if (n==0) return NULL;
tree *root= new root;
root->l= createBSTfromDLL(n/2);
root->val= head->val;
head= head->next;
root->r=createBSTfromDLL(n/2);
return root;
}
First of all the question need modifications.
Two trees means two each of n node.. So the Algo is pretty easy for O (n).
Steps :-
1> Visit all node of tree One and push them in queue Q. i.e. O(n) // n is the no. of node in tree 1.
2> For each value in queue Q.
dequeue the value from the queue Q.
Now put this value into the Tree 2 using the BST rule.
end of For // O(m).. // m is the no of node in tree 2
So total time complexity is O(T)=O(n)+O(m) .
if m==n the O(n)
else if m<n
O(n)
else
O(m)
Using an InOrderTreeIterator you scan and merge the nodes in on step. Then the list can be rearranged into a tree by using the 'reverse mergesort' suggested further up. If you use the original nodes you need to be careful since the old parent-children links still exist.
They need to be reset. Merge: O(m+n), Insert: O(m+n)
public Node createBinarySearchTreeFromSortedNodeList(List<Node> nodeList) {
return this.createBinarySearchTreeFromSortedNodeListRecursive(nodeList, 0, nodeList.size() - 1);
}
private Node createBinarySearchTreeFromSortedNodeListRecursive(List<Node> nodeList, Integer minIndex, Integer maxIndex) {
Node node = null;
if (maxIndex > nodeList.size() - 1 || minIndex < 0)
return null;
if (minIndex == maxIndex) {
node = nodeList.get(minIndex);
node.setLeftChild(null);
node.setRightChild(null);
node.setParent(null);
return node;
}
else
if (minIndex > maxIndex)
return null;
Integer middle = (maxIndex + minIndex) / 2;
Node leftChild = createBinarySearchTreeFromSortedNodeListRecursive(nodeList, minIndex, middle - 1);
Node rightChild = createBinarySearchTreeFromSortedNodeListRecursive(nodeList, middle + 1, maxIndex);
node = nodeList.get(middle);
node.setLeftChild(leftChild);
node.setRightChild(rightChild);
leftChild.setParent(node);
rightChild.setParent(node);
return node;
}
public class InOrderTreeIterator {
private Node currentNode = null;
private Stack<Node> treeTraverserStack = null;
private Node next = null;
public InOrderTreeIterator(Node root) {
treeTraverserStack = new Stack<Node>();
this.currentNode = root;
this.fetchNextNode();
}
public Node next() {
Node result = next;
this.fetchNextNode();
return result;
}
public boolean hasNext() {
return this.next != null;
}
private void fetchNextNode() {
Node result = null;
boolean done = false;
while (!done) {
if (!this.treeTraverserStack.isEmpty() || currentNode != null) {
if (currentNode != null) {
this.treeTraverserStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
else {
currentNode = this.treeTraverserStack.pop();
result = currentNode;
currentNode = currentNode.getRightChild();
done = true;
}
}
else
done = true;
}
this.next = result;
}
}
}
Lets say BSTs are of m and n elements respectively. By doing individual in order traversal of each BST we can get two sorted linked list of m and n elements which will be achieved in O(m) and O(n). merging these to form an array is of O(m+n). Now creating a balanced BST out of this array will again be O(m+n), we can use the simple technique shown.
- apoorvagaurav July 10, 2012