#include<stdio.h>
#include<malloc.h>

struct node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
};

typedef struct node Node;

void AddNode(Node* root, int number)
{	
	if(root->data==number)
		return;
	else if(root->data>number)
	{
		if(root->left!=NULL)
		{
			AddNode(root->left,number);
		}
		else
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = number;
			newNode->left = NULL;
			newNode->right= NULL;
			newNode->next= NULL;
			root->left = newNode;
		}
	}
	else if(root->data<number)
	{
		if(root->right!=NULL)
		{
			AddNode(root->right,number);
		}
		else
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = number;
			newNode->left = NULL;
			newNode->right= NULL;
			newNode->next= NULL;
			root->right= newNode;
		}
	}
}

Node* Populate(Node* root)
{
	if(root!=NULL)
	{
		root->next = Populate(root->right);
		if(root->left!=NULL)
		{	
			root->left->next = root;
			return Populate(root->left);
		}
		else
		{
			return root;
		}
	}
	else
	{
		return NULL;
	}
}

int main()
{
	Node* start;
	Node* root = (Node*)malloc(sizeof(Node));
	root->data = 4;
	root->left = NULL;
	root->right= NULL;
	root->next= NULL;

	AddNode(root,3);
	AddNode(root,7);
	AddNode(root,1);
	AddNode(root,2);
	AddNode(root,6);
	AddNode(root,9);
	AddNode(root,17);
	AddNode(root,11);
	AddNode(root,10);
	AddNode(root,3);
	AddNode(root,4);
	
	start = Populate(root);
	
	while(start!=NULL)
	{
		printf("%d\t",start->data);
		start = start->next;
	}
 
  return 1;
}