Converting a Binary Search Tree to a Sorted Doubly Linked List

Change the left and right pointers of each node in Binary search Tree to make it a sorted doubly linked list.

Method:
Just do the Post order traversal and while visiting the node,

•     Point the left link of visiting node to right most node in left tree.
•     Point the right link of visiting node to left most node in right tree.

[showads ad=inside_post]
But Why should We do this,

Suppose node in question is X.
Assume its left and right subtree is already converted in sorted doubly linked list.

So, now where X’s left and right pointer should point.

Left Pointer :
As all elements X’s left subtree were smaller than X, so X’s Left pointer should point to the largest among them i.e. the right most node in that sorted linked list.

Right Pointer :
As all elements X’s right subtree was greater than X, so X’s Right pointer should point to the smallest among them i.e. the left most node in that sorted linked list.

Now X’s is a part of sorted Doubly Linked List. Suppose X was the left subtree of Node Y (Y is parent of X).
So, Y’s left subtree is now a sorted linked list.

Now perform same steps on Z i.e. the Right subtree of Y.

Now keep doing same thing in upward direction in tree and when root is done your binary search tree will be converted into sorted doubly linked list..

Hint: Leaf Node’s left and right subtrees are NULL, so consider leaf nodes as already sorted List.

Thats why Post Order Traversal is chosen because in this we first visits the left subtree, then the right  subtree and then the node itself.

Code is as follows

class BSTtoLinkListConvertor
{	
public:
	node * getRightMost(node * pRoot)
	{
		if(pRoot && pRoot->pRight)
			return getRightMost(pRoot->pRight);
		return pRoot;	
	}
	node * getLeftMost(node * pRoot)
	{
		if(pRoot && pRoot->pLeft)
			return getLeftMost(pRoot->pLeft);
		return pRoot;	
	}
	void convert(node * pRoot)
	{
		if(pRoot == NULL)
			return;
			
		convert(pRoot->pLeft);
		
		convert(pRoot->pRight);
		
		node * pNode = getRightMost(pRoot->pLeft);
		if(pNode)
		{
			pNode->pRight = pRoot;
			pRoot->pLeft = pNode;
		}
		
		pNode = getLeftMost(pRoot->pRight);
		if(pNode)
		{
			pNode->pLeft = pRoot;
			pRoot->pRight = pNode;
		}
		
	}
	
};

Usage Detail :

node * pRoot = createTree();
BSTtoLinkListConvertor bstConvertor;
bstConvertor.convert(pRoot);

// Make pTemp to point the start of Sorted Doubly Linked List	
node * pTemp = pRoot;
while(pTemp->pLeft != NULL)
{
	pTemp = pTemp->pLeft;	
}
//Printing the List
while(pTemp != NULL )
{
	std::cout<< pTemp->value << " ";
	pTemp = pTemp->pRight;	
}

Node Structure :

typedef struct node
{
	int value;
	node * pLeft;
	node * pRight;
}node;