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

void MarkSibling(Node* root, Node* firstChild)
{
	if(root==NULL||firstChild==NULL)
		return;	
	Node *nextFirstChild = NULL,*rootTemp,*currChild;
	currChild = firstChild;
	
	printf("\n%d\t",currChild->data);
	if(root->right!=NULL)
	{
		currChild->next = root->right;
		if(nextFirstChild==NULL&&currChild->left!=NULL)
			nextFirstChild = currChild->left;
		else if(nextFirstChild==NULL&&currChild->right!=NULL)
			nextFirstChild = currChild->right;
		currChild = currChild->next;
		printf("%d\t",currChild->data);
	}

	rootTemp = root->next;
	
	while(rootTemp!=NULL)
	{
		if(rootTemp->left!=NULL)
		{	
			currChild->next = rootTemp->left;
			if(nextFirstChild==NULL&&currChild->left!=NULL)
				nextFirstChild = currChild->left;
			else if(nextFirstChild==NULL&&currChild->right!=NULL)
				nextFirstChild = currChild->right;
			currChild = currChild->next;
			printf("%d\t",currChild->data);	
		}
		if(rootTemp->right!=NULL)
		{	
			currChild->next = rootTemp->right;
			if(nextFirstChild==NULL&&currChild->left!=NULL)
				nextFirstChild = currChild->left;
			else if(nextFirstChild==NULL&&currChild->right!=NULL)
				nextFirstChild = currChild->right;
			currChild = currChild->next;
			printf("%d\t",currChild->data);	
		}
		rootTemp = rootTemp->next;
	}
	if(nextFirstChild==NULL&&currChild->left!=NULL)
		nextFirstChild = currChild->left;
	else if(nextFirstChild==NULL&&currChild->right!=NULL)
		nextFirstChild = currChild->right;
	
	currChild->next = NULL;
	MarkSibling(firstChild,nextFirstChild);
}


int main()
{
	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);
	
	printf("%d/n",root->data);
	if(root->left!=NULL)
		MarkSibling(root,root->left);
	else
		MarkSibling(root,root->right);

 
  return 0;
}