CareerCup

.leetcode.com/2010/11/convert-binary-search-tree-bst-to.html

cslibrary.stanford.edu/109/TreeListRecursion.html

public TreeNode[] linkSubTree(TreeNode root) {
TreeNode[] pair = new TreeNode[2];
if (root.left.left == null && root.left.right == null) {
root.left.right = root;
pair[0] = root.left;
} else {
TreeNode[] leftSub = linkSubTree(root.left);
pair[0] = leftSub[0];
root.left = leftSub[1];
leftSub[1].right = root;
}
if (root.right.left == null && root.right.right == null) {
root.right.left = root;
pair[1] = root.right;
} else {
TreeNode[] rightSub = linkSubTree(root.right);
pair[1] = rightSub[1];
root.right = rightSub[0];
rightSub[0].left = root;
}
return pair;
}

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

typedef struct tree_node * ptr_to_node;

ptr_to_node root=NULL;
ptr_to_node head=NULL;
ptr_to_node temp2;

void convertolist(ptr_to_node temp)
{
	if(temp->left !=NULL)
   	convertolist(temp->left);
   if(head==NULL)
   	head=temp2=temp;
   else
   {
   	temp2->right=temp;
   	temp->left=temp2;
      temp2=temp;
   }
	if(temp->right !=NULL)
   	convertolist(temp->right);
}

In order traversal and build linked list

simple jst traverse inorder and for any node make left node as inorder predecessor and for right node point it to inorder successor

TreeNode * ConvertToDoublyLinkedList(TreeNode * root)
{
if(NULL == root)
return NULL;

TreeNode * left = ConvertToDoublyLinkedList(root->left);
// root's left is the rightmost element of the left sub tree
TreeNode * leftTemp = left;
while(leftTemp && leftTemp->right)
leftTemp = leftTemp->right;
root->left = leftTemp;

if(leftTemp)
leftTemp->right = root;

TreeNode * right = ConvertToDoublyLinkedList(root->right);
// root's right is the leftmost element of the right sub tree
TreeNode * rightTemp = right;
while(rightTemp && rightTemp->left)
rightTemp = rightTemp->left;
root->right = rightTemp;

if(rightTemp)
rightTemp->left = root;

return root;
}

The final root points to the actual root in the BST. you can traverse left or right to reach the front or the end of the doubly linked list.

I am using the "left" and "right" members for the "prev" and "next".