CareerCup

BST2DLL(root,start)
{
        static Node* prevNode;
	if(root)
	{
		BST2DLL(root->left);
		if(!start)
			start=root;
		else
		{
			prevNode->next=root;
			root->prev=prevNode;
		}
		prevNode=root;
		BST2DLL(root->right);
	}
}

Call BST2DLL(root,start);
Where start is the head of the DLL.

public static class BiNode
    {
        public BST.Node first, last;
    }
    
    public static BiNode convert(BST.Node root)
    {
        BiNode ret= new BiNode();
        BiNode fl= new BiNode();
        if(root.left!=null)
        {
            fl= convert(root.left);
            fl.last.right= root;
            root.left= fl.last;
        }
        
        ret.first= fl.first!=null?fl.first:root;
        
        if(root.right!=null)
        {
            fl= convert(root.right);
            fl.first.left= root;
            root.right= fl.first;
        }
        
        ret.last= fl.last!=null?fl.last:root;
        
        return ret;
    }

Use In-order traversal to build linked list

// tree2.cpp : Defines the entry point for the console application.
//



#include "stdafx.h"

#include "stdlib.h"
#include "stdio.h"
#include "string.h"

struct node
{
int data;
struct node* left;
struct node *right;
};

struct link
{
int data;
struct link* next;
struct link* pre;
};

struct node* root;

struct link *head;

void insert(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=(struct node*)malloc(sizeof(struct node));
(*root)->data=data;
(*root)->left=NULL;
(*root)->right=NULL;
}
else
{
if(((*root)->data) > data)
insert(&((*root)->left),data);
else
insert(&((*root)->right),data);
}
}

void build_link(struct link **head,int data)
{
struct link *temp=NULL,*temp1=NULL;
if((*head)==NULL)
{
(*head)=(struct link*)malloc(sizeof(struct link));
(*head)->data=data;
(*head)->next=NULL;
(*head)->pre=NULL;
}
else
{
temp1=(*head);
while((temp1->next)!=NULL)
temp1=temp1->next;

temp=(struct link*)malloc(sizeof(struct link));
temp->data=data;
temp->next=NULL;
temp->pre=temp1;
temp1->next=temp;
}
}


void inorder(struct node *root)
{
if(root==NULL)
return;
inorder(root->left);
printf("%d",root->data);
build_link(&head,root->data);
inorder(root->right);
}


void main()
{
struct link* temp;

root=NULL;
int arr[10]={4,5,6,7,1,2,10,9,8};
int i=0;

while(i<10)
{
insert(&root,arr[i]);
i++;
}
inorder(root);

temp=head;
while(temp)
{
printf("\n%d",temp->data);
temp=temp->next;
}
return;
}

delete the minimum node from tree (by removing the leftmost node, which is easy) and then insert the node at the end of the linked list.

node * deleteSmallest(node *root) {
    node* temp = root;
    node* ptemp = NULL;
    while(temp->left != NULL) {
        ptemp = temp;
        temp = temp->left;
    }
    ptemp->left = temp->right; //temp->left is always NULL.
    return temp;
}

/* This function will return a linked list */
node* insertLeastNode(node *root) {
    node *head = deleteSmallest(node *root);
    node *running_node = head;    
    while((running_node->left = deleteSmallest(node *root)) != NULL) {
        running_node = running_node->left;
    }
    return head;
}

Just in case we want our tree back, we have to point node->right of linked list to the parent.

we can call inorder traversal and as every node is visited add to the DLL.

void inorder( *root )
{
if( root==NULL)
return;
else
{
inorder( root->leftchild)
DLL( root->data );
inorder( root->rightchild );
}

void DLL(int t )
{
node* n;
n=new node;
n->data=t;
n->next=n->prev=NULL;
if ( list==NULL )
list=n;
else
{
n->next=list;
list->prev=n;
list=n;
}
}

Perform a modified version of in-order traversal. When processing the node, update the current node's right pointer to point back to the head and the head's left pointer to point to the current node.

This is modified inorder traversal converting BST to DLL.

bsttodll(struct node *root,struct node **prev,struct node **head)
{
if(root==NULL)
return;
bsttodll(root->left,prev,head);
if(*prev==NULL)
{
(*head)=root;
*prev=*head;
}
else
{
root->left=(*prev);
(*prev)->right=root;
*prev=root;
}
bsttodll(root->right,prev,head);

}


the call to the function will be bsttodll(root,NULL,NULL);

This is modified inorder traversal converting BST to DLL.

bsttodll(struct node *root,struct node **prev,struct node **head)
{
	if(root==NULL)
		return;
	bsttodll(root->left,prev,head);
	if(*prev==NULL)
	{
		(*head)=root;
		*prev=*head;
	}
	else
	{
		root->left=(*prev);
		(*prev)->right=root;
		*prev=root;
	}
	bsttodll(root->right,prev,head);	
	
}

the call to the function will be bsttodll(root,NULL,NULL);

perform iterative inorder traversal of the tree and arrange the left and right pointers accordingly!
inorder(NODEPTR start)
{
NODEPTR ptr=start;
NODEPTR prev;
while(1)
{
while(ptr->left!=NULL)
{
push(ptr);
ptr=ptr->left;
}
while(ptr->right==NULL)
{
if(prev==NULL)
{
start=ptr;//first node that is smallest node
prev=ptr;
}
else
{
ptr->left=prev;
prev->right=ptr;
prev=ptr;
}
if(stackempty())
return start;
ptr=pop();
}
prev->right=ptr;
ptr->left=prev;
prev=ptr;
ptr=ptr->right;
}//end of infinite while loop

1.traverse leftmostpath make last leaf node start=temp
2.while(temp!=NULL){
temp->next=inordersuccessor(temp);
temp->next->prev=temp;
temp=inordersuccessor(temp)
}
temp->next=NULL;

public void treeToDoublyLinkedList() {
		TreeNode head = null;
		TreeNode prev = null;
		treeToDoublyLinkedListT(root, head, prev);
	}

	private void treeToDoublyLinkedListT(TreeNode p, TreeNode head,
			TreeNode prev) {
		if (p == null) {
			return;
		}

		treeToDoublyLinkedListT(p.left, head, prev);
		p.left = prev;
		
		if (prev != null) {
			prev.right = p;
		} else {
			head = p;
		}

		TreeNode right = p.right;
		head.left = p;
		p.right = head;
		
		prev = p;
		treeToDoublyLinkedListT(right, head, prev);
	}