## Amazon Interview Question

- 0of 0 votes
Convert a BST to sorted doubly linked list.

**Country:**India

```
public TreeNode asDoublyLinkedList(TreeNode root){
if(root.leftChild == null && root.rightChild == null){
return root;
}
else {
TreeNode tmp = null;
tmp = asDoublyLinkedList(root.leftChild);
while(tmp.rightChild != null)
tmp = tmp.rightChild;
tmp.rightChild = root;
root.leftChild = tmp;
tmp = asDoublyLinkedList(root.rightChild);
while(tmp.leftChild != null)
tmp = tmp.leftChild;
tmp.leftChild = root;
root.rightChild = tmp;
}
return root;
}
```

This works but the root pointer will still point to the root of the tree. Do a while root = root.leftChild and finally the root shall point to the head of doubly linked list.

Comment from OP:

Tweaked inorder traversal and gave the below answer

```
BST to sorted LL
p = root;
visited = NULL;
do
{
while( p!=NULL )
stack.push(p);
p = p->left;
while( !stack.empty() )
{
temp = stack.pop()
visit(temp);
if( visited != NULL )
visited->right = temp;
temp->left = visited;
visited = temp;
if( temp->right )
p = temp->right;
break;
}
while( p!= NULL || !stack.empty() );
```

You need to an inorder traversal(which takes up O(n) space) to realize the sortedness of the number. Having said that, is there any way to do this in O(1) space?

public static DoublyLinkedList<E> returnSortedDoublyLinkedListFromBST(TreeNode rootNode){

if(rootNode != null){

returnSortedDoublyLinkedListFromBST(rootNode.left);

doublyLinkedList.insertLast(new E(rootNode.data));

returnSortedDoublyLinkedListFromBST(rootNode.right);

}

return doublyLinkedList;

}

Now the insertLast method in DoublyLinked List is

public void insertLast(E data){

this.addBefore(tail, data);

}

private void addBefore(DoublyLinkedListNode<E> referenceNode, E data){

DoublyLinkedListNode<E> previous = this.getPreviousNode(referenceNode);

DoublyLinkedListNode<E> next = referenceNode;

DoublyLinkedListNode<E> newNode = new DoublyLinkedListNode<E>(previous,next,data);

next.setPrevious(newNode);

previous.setNext(newNode);

size ++;

}

Another recursive method... use inorder traversal

BST2DLL(node *root, List ** head,List **tail)

{

if(!root)

return Null;

//convert left subtree

BST2DLL(root->left,&head,&tail);

//add the root node to the list

if(!*last) // if this is the left most node

{

*head=root;

*last=*head;

}

else

{

*tail -> right=root;

root->left=*tail;

*tail=root;

}

BST2DLL(root->right,&head,&tail);

}

A recursive solution can be found

```
int BST2DLL(node** root)
{
stack<node*> s;
node* p = *root;
while(p -> lchild)
{
s.push(p);
p = p -> lchild;
}
//dummy head;
node* head = (node*)malloc(sizeof(node));
if (!head) return 0;
head -> lchild = head;
head -> rchild = head;
node* tail = head;
while(!IsEmpty(s))
{
node* tp = pop(s);
// link
tail -> rchild = tp;
tp -> lchild = tail;
tail = tp;
if(tp - > rchild)
{
node* ttp = tp -> rchild;
while(ttp)
{
push(ttp);
ttp = ttp->lchild;
}
}
}
tail -> rchild = head;
head -> lchild = tail;
return 1;
}
```

private static void inorder(BSTNode node) {

if (node.getLeft() != null)

inorder(node.getLeft());

//System.out.println(node.getData());

sortedList.add(node.getData());

if (node.getRight() != null)

inorder(node.getRight());

}

private static void traverse() {

ListIterator dll = sortedList.listIterator();

System.out.println("Forward traversing");

while (dll.hasNext())

System.out.println(dll.next());

System.out.println("==============================");

System.out.println("Backward traversing");

while (dll.hasPrevious())

System.out.println(dll.previous());

}

void treetodoublelist(struct node *root, struct node **head, struct node **tail) {

struct node *temp = NULL;

if(root != NULL) {

treetodoublelist(root->left,head,tail);

if(*head == NULL && *tail == NULL) {

*head = (struct node *)malloc(sizeof(struct node));

(*head)->left = NULL;

(*head)->right = NULL;

(*head)->data = root->data;

*tail = *head;

}

else {

temp = (struct node *)malloc(sizeof(struct node));

temp->left = (*tail);

temp->right = NULL;

temp->data = root->data;

(*tail)->right = temp;

*tail = temp;

}

treetodoublelist(root->right,head,tail);

}

}

```
void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
treetodoublelist(root->left,head,tail);
if(*head == NULL && *tail == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
(*head)->left = NULL;
(*head)->right = NULL;
(*head)->data = root->data;
*tail = *head;
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
treetodoublelist(root->right,head,tail);
}
}
```

```
public TreeNode convert(TreeNode node)
{
if(node== null)
return null;
if(node.leftchild==null && node.rightchild== null)
return node;
else
{ TreeNode temp = null;
temp = convert(node.leftchild);
if(temp!=null)
{
while(temp.rightchild!=null)
temp= temp.rightchild;
temp.rightchild = node;
node.leftchild = temp;
}
temp = convert(node.rightchild);
if(temp!=null)
{
while(temp.leftchild!=null)
temp = temp.leftchild;
temp.leftchild = node;
node.rightchild = temp;
}
}
return node;
}
```

- Anonymous on April 08, 2012 Edit | Flag Reply