## Amazon Interview Question

Software Engineer / Developers**Country:**India

```
//Let T be the root node of bst tree.
main(){
start=createNew(-Infinity);
end=createNew(+Infinity);
start->prev=null;
start->next=end;
end->next=null;
end->prev=start;
bstToLLRight(T,start);
}
bstToLLRight(T,L){
if(T!=null){
node=createNew(T.value);
node->prev=L;
node->next=L->next;
L->next->prev=node;
L->next=node;
bstToLLLeft(T->left,node);
bstToLLRight(T->right,node);
}
}
bstToLLLeft(T,L){
if(T!=null){
node=createNew(T.value);
node->next=L;
node->prev=L->prev;
L->prev->next = node;
L->prev = node;
bstToLLLeft(T->left,node);
bstToLLRight(T->right,node);
}
}
```

Even recursion is not considered as constant space(becuase of space taken in stack for each function call), I guess we have to use recursion to iterate through a tree.

```
void BSTtoDLL(node* root, node* &left, node* &right){
if ( root ){
node *left1=0,*right1=0,*left2=0,*right2=0;
BSTtoDLL(root->left,left1,right1);
BSTtoDLL(root->right,left2,right2);
if(right1){
right1->right=root;
root->left=right1;
}
if(left2){
root->right=left2;
left2->left=root;
}
if (left1)
left=left1;
else
left = root;
if (right2)
right=right2;
else
right=root;
}
}
```

i have done it by using an array with two indices (like queue). can i make use of that as it is stated to use constant space.

Algo i had used...

1. make an inorder traversal...

2. store all the addresses of tree's node in an array (queue)..

3. assign

q[i]->left=q[i+1];

q[i]->right=q[i-1];

4. head of dll = q[0]

i only want to know that can i use extra array here on not....??

Here is my solution. It may not be efficient with time complexity

```
private void convertToDLLinkedList(TreeNode node) {
if (node != null ) {
if (node.getLeftNode() != null) {
convertToDLLinkedList(node.getLeftNode());
TreeNode temp = node.getLeftNode();
while (temp.getRightNode() != null) {
temp = temp.getRightNode();
}
temp.setRightNode(node);
node.setLeftNode(temp);
}
if (node.getRightNode() != null) {
convertToDLLinkedList(node.getRightNode());
TreeNode temp = node.getRightNode();
while (temp.getLeftNode() != null) {
temp = temp.getLeftNode();
}
temp.setLeftNode(node);
node.setRightNode(temp);
}
}
}
```

It can be done in O(n) time and using constant space by using two functions: find_successor(node * ptr) and find_predecessor(node * ptr). Both these functions run using constant space.I am assuming that nodes of the tree are modifiable into nodes of a DLL.

BST_to_DLL(node * root)

{

node *head,*tail,ptr;

head=tail=NULL;

if(root!=NULL){head=tail=root;}

while((ptr=find_predecessor(head))!=NULL)

{

ptr->next=head;

head->prev=ptr;

head=ptr;

}

while((ptr=find_successor(tail))!=NULL)

{

tail->next=ptr;

ptr->prev=tail;

tail=ptr;

}

return head;

}

Even I was asked this code recently in 1st round of Amazon Interview:

- anjum February 04, 2012Logic is :

1. Solve it by recurssion.

2. The left most child of a tree is the head node

3. The right most child of a tree is the last node of a DLL.

4. If only one node exists . Then the root->left=root and root->right=root;

static Node BSTtoDLL(Node root)

{ Node head,tail;

if(root==NULL) return NULL;

head=BSTtoDLL(root->left);

tail=BSTtoDLL(root->right);

// code for single element

root->left=root;

root->right=root;

head=append(head,root);

head=append(head,tail);

return(head);

}

void createDLLpointers(Node a,Node b)

{

a-> left=b;

b->right=a;

}

Node append(Node a, Node b)

{

if(a==NULL) return b;

if (b=NULL) return a;

afirst=a->left; // pointers to the first elements of each list.

bfirst=b-left;

createDLLpointers(afirst,b);

createDLLpointers(bfirst,a);

return a;

}