CareerCup

Here is my implementation on this:

basicalgos.blogspot.com/2012/03/26-convert-binary-search-tree-to-sorted.html

/*
Task write the code to find the inorder succesor in binary tree (or BST)
A program to convert an ordered binary tree to doubly link list circular
*/
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left,*right;
};
typedef struct node * Node;

/*
helper function -- given two list nodes, join them
together so the second immediately follow the first.
Sets the .next of the first and the .previous of the second.
*/
static void join(Node a, Node b)
{
if(a)
a->right=b;
if(b)
b->left=a;
}


/*
helper function -- given two circular doubly linked
lists, append them and return the new list.
*/
static Node append(Node a, Node b)
{
if(!a) return b;
if(!b) return a;

Node Alast=a->left;
Node Blast=b->left;

join(Alast,b);
join(Blast,a);

return a;
}


/*
--Recursion--
Given an ordered binary tree, recursively change it into
a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {

if(!root)
return NULL;

Node alist;
Node blist;
/* recursively solve subtrees -- leap of faith! */
alist=treeToList(root->left);
blist=treeToList(root->right);

/* Make a length-1 list ouf of the root */
root->left=root;
root->right=root;

/* Append everything together in sorted order */
alist=append(alist,root);
alist=append(alist,blist);

}

/* Create a new node */
static Node newNode(int data)
{
Node node=(Node) malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
}


/* Add a new node into a tree */
static void treeInsert(Node* rootRef, int data)
{
Node root = *rootRef;
if (root == NULL) *rootRef = newNode(data);
else
{
if (data <= root->data)
treeInsert(&(root->left), data);
else
treeInsert(&(root->right), data);
}
}


void printList(Node head)
{
if(head==NULL)
printf("hello");
Node current;
current=head;
while(current)
{
printf("%d",current->data);
current=current->right;
if(current==head)
break;
}
}
void printTree(Node root)
{
if(!root)
return;
if(root)
{
printTree(root->left);
printf("%d ",root->data);
printTree(root->right);
}
}
/* Demo that the code works */
int main() {
Node root = NULL;
Node head;
treeInsert(&root, 4);
treeInsert(&root, 2);
treeInsert(&root, 1);
treeInsert(&root, 3);
treeInsert(&root, 5);
printTree(root);
head = treeToList(root);
printf("\nlist\n");
printList(head); /* prints: 1 2 3 4 5 */
int i;
scanf("%d",&i);
return(0);
}

//By using inorder traversal,and maintaining a pointer to the previous node in inorder
//we can construct DLL
void dll(node *root,node **prev,node **head)
{
     if(root)
     {
     
     dll(root->left,prev,head);
     root->left=(*prev);
     
     if(*prev)
              (*prev)->right=root;
     else
         *head=root;
     
     (*prev)=root;
     dll(root->right,prev,head);
     }
     }
node * fun(node *root)
{
     node *prev=NULL;
     node *head=NULL;
     dll(root,&prev,&head);
     return head;
     }

Here is a recursive solution using modified in-order traverse (in C#)
The signature of method is "void BSTToDLL(ref Node root, ref Node head)"
1. if root is null then return
2. call "BSTToDLL(ref root.rchild, ref head)" to convert right sub-tree of root to be DLL and update head
3. if head is not null then set head.lchild=root and root.rchild=head
4. set head=last
5. call "BSTToDLL(ref root.lchild, ref head)" to convert left sub-tree of root to be DLL and update head
When you finish the routine you will get the head of DLL with head.lchild=null and the tail's rchild=null. So all you need is to use another method to call the routine above and set these two values.

node ** next = &head;
node** prev =NULL;
bst_to_doubly(node * root)
{
if(root == NULL)
return;
bst_to_doubly(root->left);
link * node = (node*)malloc(sizeof(node));
node->data = root->data;
node->prev=*prev;
*prev=node;
*next=node;
next=&(node->next);
bst_to_doubly(root->right);

}

//here root will be BST root node.
//At start just store null into fst (first) and lst (last), and call convertToList (&root,&fst,&lst).
//At the end of execution of convertToList they will have first and last nodes of the DLL respectively.

void convertToList(node **root,node **fst,node **lst)
{
node *temp;
if((*root)->left==NULL && (*root)->right == NULL)
{
*fst = *root;
*lst = *root;
return;
}

if((*root)->left != NULL)
{
convertToList(&((*root)->left),fst,lst);
(*root)->left = *lst;
(*lst)->right = *root;
temp = *fst;
}

if((*root)->right !=NULL)
{
convertToList(&((*root)->right),fst,lst);
(*root)->right = *fst;
(*fst)->left = *root;
}
else
{
*lst = *root;
}

if((*root)->left == NULL)
*fst = *root;
else
*fst = temp;
}

Am I missing something here. Isn't this as easy as performing an inorder traversal
And when we "visit" each node. Just add it to the end of the linked list.