#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)
{
   while(root!=NULL&&firstChild!=NULL)
   {	
	Node *nextFirstChild = NULL,*rootTemp,*currChild;
	currChild = firstChild;
	
	printf("\n%d\t",currChild->data);
	if(root->right!=NULL&&root->right->data!=firstChild->data)
	{
		currChild->next = root->right;
		if(nextFirstChild==NULL&&currChild->left!=NULL)
		{
			nextFirstChild = currChild->left;
			firstChild = currChild;
		}
		else if(nextFirstChild==NULL&&currChild->right!=NULL)
		{
			nextFirstChild = currChild->right;
			firstChild = currChild;
		}
		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;
				firstChild = currChild;
			}
			else if(nextFirstChild==NULL&&currChild->right!=NULL)
			{
				nextFirstChild = currChild->right;
				firstChild = currChild;
			}
			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;
				firstChild = currChild;
			}
			else if(nextFirstChild==NULL&&currChild->right!=NULL)
			{
				nextFirstChild = currChild->right;
				firstChild = currChild;
			}
			currChild = currChild->next;
			printf("%d\t",currChild->data);	
		}
		rootTemp = rootTemp->next;
	}
	if(nextFirstChild==NULL&&currChild->left!=NULL)
	{
		nextFirstChild = currChild->left;
		firstChild = currChild;
	}
	else if(nextFirstChild==NULL&&currChild->right!=NULL)
	{
		nextFirstChild = currChild->right;
		firstChild = currChild;
	}
	
	currChild->next = NULL;
	root = firstChild;
	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",root->data);
	if(root->left!=NULL)
		MarkSibling(root,root->left);
	else
		MarkSibling(root,root->right);

 
  return 0;
}