Amazon Interview Question
Software Engineer in TestsCountry: India
Interview Type: Written Test
public DNode convertBinaryTreeToDLL(Node root)
{
if(root==null)
{
return null;
}
DNode head=null;
DNode tail=null;
if(root.left!=null)
{
DNode lhead=convertBinaryTreeToDLL(root.left);
DNode ltail=lhead.prev;
ltail.next=null;
lhead.prev=null;
head=lhead;
tail=ltail;
}
DNode node=new DNode(root.data);
if(head==null)
{
head=tail=node;
}
else
` {
tail.next=node;
node.prev=tail;
tail=node;
}
if(root.right!=null)
{
DNode rhead=convertBinaryTreeToDLL(root.right);
DNode rtail=rhead.prev;
rtail.next=null;
rhead.prev=tail;
tail.next=rhead;
tail=rtail;
}
head.prev=tail;
tail.next=head;
return head;
}
DNode process(Node root)
{
DNode node=convertBinaryTreeToDLL(root);
if(node!=null)
{
DNode tail=node.prev;
tail.next=null;
node.prev=null;
}
return node;
}
The above algorithm takes O(n) time. Please let me know if you find anything incorrect either in logic or in the time complexity mentioned.
This is just a traversal. I chose pre-order b/c it made returning the Linked List easier. In Ruby!!
class << self
attr_accessor :linked_list
end
def self.convert_to_doubly_linked_list(root, current_pointer=nil)
return linked_list unless root
unless current_pointer
self.linked_list = LinkedList.new
linked_list.head = current_pointer = ListElement.new(root.value)
end
current_pointer.previous = ListElement.new(root.left.value) if root.left
current_pointer.next = ListElement.new(root.right.value) if root.right
convert_to_doubly_linked_list(root.left, current_pointer.previous)
convert_to_doubly_linked_list(root.right, current_pointer.next)
end
O(n) b/c it's a traversal.
>> head
=> ListElement: data = 100
>> head.next.next
=> ListElement: data = 175
>> head.previous.previous
=> ListElement: data = 25
This question (as is usual on any BST problem) is made for recursion. The trick is to pass a copy of the previous node to all subsequent recursive calls. Of course, when you start, there is no previous, so it should be set to NULL.
Here is the code:
Node * treeToDll(Tree* r, Node* pr) {
if (!r) //The previous node is returned
return pr;
Node* prev = treeToDll(r->left, pr);
Node* c = new Node(r->val);
if (prev) prev->next = c;
c->prev = prev;
return treeToDll(r->right, c); // Return the rightmost node, but if it does not
// exist then return the current node (c)
}
Yes, it's that simple! I urge you guys to try this code out (by hand or even better in any tree example that you could whip up). You will see that it works beautifully.