Convert a binary search tree into circular doubly linked list

The Challenge
The challenge is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it.

#include <iostream>

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

void insert(tree_node **current, int data ) {
	if ( *current == (tree_node*)0 ) {
		*current = new tree_node();
		(*current)->left  = ( tree_node *) 0;
		(*current)->right = ( tree_node *) 0;
		(*current)->data  = data;
	} else {
		if ( data < (*current)->data )  {
			insert ( &((*current)->left) , data );
		} else {
			insert ( &((*current)->right), data );
		}
	}
}
void print_tree(tree_node *current) {
	if ( ! current ) 
		return;
	print_tree(current->left );
	std::cout << current->data << " ";
	print_tree(current->right);

}
struct dlist {
	dlist *left;
	dlist *right;
	int data;
};

dlist *head = (dlist *)0;
dlist *cur  = ( dlist *)0;

void create_dlist(tree_node *current) {
	if ( ! current ) {		
		return;
	}
	create_dlist( current->left);
	if ( ! head ) {
		head = new dlist;
		head->left = ( dlist *) 0;
		head->right = ( dlist *) 0;
		head->data  = current->data;		
		cur = head;
	} else {
		dlist *temp = new dlist;

		temp->right = ( dlist *)0;
		temp->left  = cur;
		temp->data  = current->data;

		cur->right  = temp;

		cur = temp;
	}
	create_dlist( current->right);
	cur->right = head;
	head->left = cur;
}

void print_dlist() {
    std::cout << std::endl;
	dlist *current = head;
	while ( current->right != head ) {
		std::cout << current->data << " ";
		current = current->right;
	}
    std::cout << current->data;
    std::cout << std::endl;
}


int main( int argc, char** argv) {
	int arr[] = {5,2,7,1,8,3,9};
	int len = sizeof(arr)/sizeof(arr[0]);
	tree_node *my_tree =  ( tree_node *)0;
	for ( int i = 0; i < len; i++ ) {
		insert(&my_tree, arr[i]);
	}
	print_tree(my_tree);	
	create_dlist(my_tree);
	print_dlist();
	return 0;
}
Advertisements

One thought on “Convert a binary search tree into circular doubly linked list

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s