Ronzii's Blog

Just your average geek's blog

Convert Tree into Sorted Circular Doubly Linked List

struct node
{
	int value;
	struct node* left;
	struct node* right;
};
typedef struct node Node;
// Previous tracks the parent
// Head tracks the head of the Circular DLL
Node* treeToList(Node* current, Node* &previous=NULL, Node* &head=NULL)
{
	if(current==NULL)
	{
		return 0;
	}
	treeToList(current->left,previous,head);
	current->left = previous;
	if(previous)
	{
		previous->right = current;
	}
	else
	{
		// Left most node is head of list
		head = current;
	}
	// Save right subtree pointer for recursive call
	Node* right = current->right;
	// Make list circular
	head->left = current;
	current->right = head;
	previous = current;
	treeToList(right,previous,head);
}
Advertisements

February 27, 2012 - Posted by | C++ | , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s