Ronzii's Blog

Just your average geek's blog

Convert Sorted Circular Doubly Linked List into a Balanced Search Tree

struct node
{
	int value;
	struct node* previous;
	struct node* next;
};
typdef struct node Node;
Node* getMiddle(Node* front)
{
	if(front==NULL)
	{
		return NULL;
	}
	else
	{
		Node* slow = front;
		Node* fast = front->previous;
		do
		{
			fast = fast->next->next;
			slow = slow->next
		}while(fast->value > slow->value && fast!=end && fast!=start);
		return slow;
	}
}
Node* convertDLLToTree(Node* front)
{
	// In case of empty list
	if(front==NULL)
	{	
		return NULL;
	}
	// Single Node - Base Case
	else if(front==front->next && front==front->previous)
	{	
		return front;
	}
	else
	{
		// Get Middle
		Node* middle = getMiddle(front);
		// partition into 2 DLL centered at middle
		middle->previous->next = front; // front->previous = middle->previous
		front->previous->next = middle->next; //
		// Find middle of sub DLL
		middle->previous = convertDLLToTree(front);
		middle->next = convertDLLToTree(middle->next);
		return middle;
	}
}
Advertisements

February 27, 2012 Posted by | C++ | , , , , | Leave a comment

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);
}

February 27, 2012 Posted by | C++ | , , , , | Leave a comment