CareerCup

Even I was asked this code recently in 1st round of Amazon Interview:
Logic 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;
}

Can anybody explain how this code is running

//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);
}
}

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;
}

Morris traversal (inorder traversal of BST without stack or recursion),