Convert Binary tree into Linked list

Structure of nodes in both doubly linked list and binary search tree are same.So we need to arrange the pointers among the nodes.We can use recursive algorithm to convert BST to doubly linked list.

Algorithm :


An ordered binary tree looks like below:

a circular/doubly linked list looks like this.

if we remove the link in first node and last node of a circular linked list,t will become a doubly linked list.


Recursive algorithm which takes BST and rearranges the internal pointers to make a circular doubly linked list.The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list.

Algorithm:

If tree is not empty

Convert left subtree to List, let hLeft points to it
Convert right subtree to List, let hRight points to it
Append hLeft with root and then hRight

For detailed explanation have a look at this link :

http://www.rawkam.com/?p=1139

Convert linked list into binary search tree:
If it sorted list,we can do the reverse engineering from conversion of tree to linked list.

If the list is not empty.
 Middle element of the list will become root of the element.
Recursively construct the BST from left and right parts of the linked list.Left and right parts of list will become left and right branches of tree.

In place conversion of sorted doubly linked list to balanced BST : http://www.geeksforgeeks.org/archives/17629

Sorted linked list to balanced BST : http://www.geeksforgeeks.org/archives/17063