#include<stdio.h>
#include<math.h>
#include<stdlib.h>
struct tnode
{
	int data; char color;
	struct tnode* parent; 
	struct tnode* rightChild;
	struct tnode* leftChild;
};
struct tree
{
	struct tnode* root;
	struct tnode* nil;
};


struct tnode* createnode(int data)
{
	struct tnode *newnode;
	newnode=(struct tnode*)malloc(sizeof(struct tnode));
	newnode->data=data;
	newnode->color='R';
	newnode->leftChild=NULL;
	newnode->parent=NULL;
	newnode->rightChild=NULL;
	return newnode;
}

void leftrotate(struct tree*T, struct tnode*x)
{
	struct tnode * y;
	y=(struct tnode*)malloc(sizeof(struct tnode));
	y=x->rightChild;
	x->rightChild=y->leftChild;
	if(y->leftChild!=T->nil)
		y->leftChild->parent=x;
	else if (x==x->parent->leftChild)
		x->parent->leftChild=y;
	else 
		x->parent->rightChild=y;
	
	y->leftChild=x;
	x->parent=y; 
}
void rightrotate(struct tree*T, struct tnode*x)
{
	struct tnode * y;
	y=(struct tnode*)malloc(sizeof(struct tnode));
	y=x->leftChild;
	x->leftChild=y->rightChild;
	if(y->rightChild!=T->nil)
		y->rightChild->parent=x;
	else if (x==x->parent->rightChild)
		x->parent->rightChild=y;
	else 
		x->parent->leftChild=y;
	
	y->rightChild=x;
	x->parent=y; 
}
void rbinsertfixup(struct tree*T, struct tnode*z)
{
	struct tnode*y;
	y=(struct tnode*)malloc(sizeof(struct tnode));
	
	while(z->parent->color=='R')
	{
		if(z->parent==z->parent->parent->leftChild)
		{
			y=z->parent->parent->rightChild;
			if(y->color=='R')
			{
				z->parent->color='B';
				y->color='B';
				z->parent->parent->color='R';
				z=z->parent->parent;
			}
			else if(z==z->parent->rightChild)
			{
			  z=z->parent;
			  leftrotate(T,z);
			}
			z->parent->color='B';
			z->parent->parent->color='R';
			rightrotate(T,z->parent->parent);
		}
		else
		{
			y=z->parent->parent->leftChild;
			if(y->color=='R')
			{
				z->parent->color='B';
				y->color='B';
				z->parent->parent->color='R';
				z=z->parent->parent;
			}
			else if(z==z->parent->leftChild)
			{
			  z=z->parent;
			  rightrotate(T,z);
			}
			z->parent->color='B';
			z->parent->parent->color='R';
			leftrotate(T,z->parent->parent);	
		}
	}
	T->root->color='B';
}
void insertion(struct tree *T, struct tnode *z)
{
	
	struct tnode * y;
	y=(struct tnode*)malloc(sizeof(struct tnode));
	struct tnode * x;
	x=(struct tnode*)malloc(sizeof(struct tnode));
	y=T->nil; 
	x=T->root;
	while(x!=T->nil)
	{
		y=x;
		if(z->data < x->data)
		x=x->leftChild;
		else 
		x=x->rightChild;
	}
	z->parent=y;
	if(y==T->nil)
	T->root=z;
	else if (z->data< y->data)
	y->leftChild=z;
	else
	y->rightChild=z;
	
	z->leftChild=T->nil;
	z->rightChild=T->nil;
	z->color='R';
	rbinsertfixup(T,z);
	
}

void visit(struct tnode* x)
{
	if(x!=NULL)
	{
		visit(x->leftChild);
		if(x->parent!=NULL)
		printf("%d %c %d \n", x->data, x->color, x->parent->data);
		else
		printf("%d %c NIL \n", x->data, x->color);
			
		
	}
}
void pre_fix_tour (struct tree* T)
{
	if(T->root==NULL)
	printf("empty tree");
	else
	visit(T->root);
	
}


int main()
{
	int a[]={5,4,1,6,10,11};
	int i;
	struct tnode* node;
	struct tree *treen;
	treen=(struct tree*)malloc(sizeof(struct tree));
	treen->nil=NULL;
	treen->root=NULL;
	for(i=0;i<6;i++)
	{
		node=createnode(a[i]);
		insertion(treen, node);
	}
	
pre_fix_tour(treen);
	
	return 0;
	
	
	
}

I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzdGRsaWIuaD4Kc3RydWN0IHRub2RlCnsKCWludCBkYXRhOyBjaGFyIGNvbG9yOwoJc3RydWN0IHRub2RlKiBwYXJlbnQ7IAoJc3RydWN0IHRub2RlKiByaWdodENoaWxkOwoJc3RydWN0IHRub2RlKiBsZWZ0Q2hpbGQ7Cn07CnN0cnVjdCB0cmVlCnsKCXN0cnVjdCB0bm9kZSogcm9vdDsKCXN0cnVjdCB0bm9kZSogbmlsOwp9OwoKCnN0cnVjdCB0bm9kZSogY3JlYXRlbm9kZShpbnQgZGF0YSkKewoJc3RydWN0IHRub2RlICpuZXdub2RlOwoJbmV3bm9kZT0oc3RydWN0IHRub2RlKiltYWxsb2Moc2l6ZW9mKHN0cnVjdCB0bm9kZSkpOwoJbmV3bm9kZS0+ZGF0YT1kYXRhOwoJbmV3bm9kZS0+Y29sb3I9J1InOwoJbmV3bm9kZS0+bGVmdENoaWxkPU5VTEw7CgluZXdub2RlLT5wYXJlbnQ9TlVMTDsKCW5ld25vZGUtPnJpZ2h0Q2hpbGQ9TlVMTDsKCXJldHVybiBuZXdub2RlOwp9Cgp2b2lkIGxlZnRyb3RhdGUoc3RydWN0IHRyZWUqVCwgc3RydWN0IHRub2RlKngpCnsKCXN0cnVjdCB0bm9kZSAqIHk7Cgl5PShzdHJ1Y3QgdG5vZGUqKW1hbGxvYyhzaXplb2Yoc3RydWN0IHRub2RlKSk7Cgl5PXgtPnJpZ2h0Q2hpbGQ7Cgl4LT5yaWdodENoaWxkPXktPmxlZnRDaGlsZDsKCWlmKHktPmxlZnRDaGlsZCE9VC0+bmlsKQoJCXktPmxlZnRDaGlsZC0+cGFyZW50PXg7CgllbHNlIGlmICh4PT14LT5wYXJlbnQtPmxlZnRDaGlsZCkKCQl4LT5wYXJlbnQtPmxlZnRDaGlsZD15OwoJZWxzZSAKCQl4LT5wYXJlbnQtPnJpZ2h0Q2hpbGQ9eTsKCQoJeS0+bGVmdENoaWxkPXg7Cgl4LT5wYXJlbnQ9eTsgCn0Kdm9pZCByaWdodHJvdGF0ZShzdHJ1Y3QgdHJlZSpULCBzdHJ1Y3QgdG5vZGUqeCkKewoJc3RydWN0IHRub2RlICogeTsKCXk9KHN0cnVjdCB0bm9kZSopbWFsbG9jKHNpemVvZihzdHJ1Y3QgdG5vZGUpKTsKCXk9eC0+bGVmdENoaWxkOwoJeC0+bGVmdENoaWxkPXktPnJpZ2h0Q2hpbGQ7CglpZih5LT5yaWdodENoaWxkIT1ULT5uaWwpCgkJeS0+cmlnaHRDaGlsZC0+cGFyZW50PXg7CgllbHNlIGlmICh4PT14LT5wYXJlbnQtPnJpZ2h0Q2hpbGQpCgkJeC0+cGFyZW50LT5yaWdodENoaWxkPXk7CgllbHNlIAoJCXgtPnBhcmVudC0+bGVmdENoaWxkPXk7CgkKCXktPnJpZ2h0Q2hpbGQ9eDsKCXgtPnBhcmVudD15OyAKfQp2b2lkIHJiaW5zZXJ0Zml4dXAoc3RydWN0IHRyZWUqVCwgc3RydWN0IHRub2RlKnopCnsKCXN0cnVjdCB0bm9kZSp5OwoJeT0oc3RydWN0IHRub2RlKiltYWxsb2Moc2l6ZW9mKHN0cnVjdCB0bm9kZSkpOwoJCgl3aGlsZSh6LT5wYXJlbnQtPmNvbG9yPT0nUicpCgl7CgkJaWYoei0+cGFyZW50PT16LT5wYXJlbnQtPnBhcmVudC0+bGVmdENoaWxkKQoJCXsKCQkJeT16LT5wYXJlbnQtPnBhcmVudC0+cmlnaHRDaGlsZDsKCQkJaWYoeS0+Y29sb3I9PSdSJykKCQkJewoJCQkJei0+cGFyZW50LT5jb2xvcj0nQic7CgkJCQl5LT5jb2xvcj0nQic7CgkJCQl6LT5wYXJlbnQtPnBhcmVudC0+Y29sb3I9J1InOwoJCQkJej16LT5wYXJlbnQtPnBhcmVudDsKCQkJfQoJCQllbHNlIGlmKHo9PXotPnBhcmVudC0+cmlnaHRDaGlsZCkKCQkJewoJCQkgIHo9ei0+cGFyZW50OwoJCQkgIGxlZnRyb3RhdGUoVCx6KTsKCQkJfQoJCQl6LT5wYXJlbnQtPmNvbG9yPSdCJzsKCQkJei0+cGFyZW50LT5wYXJlbnQtPmNvbG9yPSdSJzsKCQkJcmlnaHRyb3RhdGUoVCx6LT5wYXJlbnQtPnBhcmVudCk7CgkJfQoJCWVsc2UKCQl7CgkJCXk9ei0+cGFyZW50LT5wYXJlbnQtPmxlZnRDaGlsZDsKCQkJaWYoeS0+Y29sb3I9PSdSJykKCQkJewoJCQkJei0+cGFyZW50LT5jb2xvcj0nQic7CgkJCQl5LT5jb2xvcj0nQic7CgkJCQl6LT5wYXJlbnQtPnBhcmVudC0+Y29sb3I9J1InOwoJCQkJej16LT5wYXJlbnQtPnBhcmVudDsKCQkJfQoJCQllbHNlIGlmKHo9PXotPnBhcmVudC0+bGVmdENoaWxkKQoJCQl7CgkJCSAgej16LT5wYXJlbnQ7CgkJCSAgcmlnaHRyb3RhdGUoVCx6KTsKCQkJfQoJCQl6LT5wYXJlbnQtPmNvbG9yPSdCJzsKCQkJei0+cGFyZW50LT5wYXJlbnQtPmNvbG9yPSdSJzsKCQkJbGVmdHJvdGF0ZShULHotPnBhcmVudC0+cGFyZW50KTsJCgkJfQoJfQoJVC0+cm9vdC0+Y29sb3I9J0InOwp9CnZvaWQgaW5zZXJ0aW9uKHN0cnVjdCB0cmVlICpULCBzdHJ1Y3QgdG5vZGUgKnopCnsKCQoJc3RydWN0IHRub2RlICogeTsKCXk9KHN0cnVjdCB0bm9kZSopbWFsbG9jKHNpemVvZihzdHJ1Y3QgdG5vZGUpKTsKCXN0cnVjdCB0bm9kZSAqIHg7Cgl4PShzdHJ1Y3QgdG5vZGUqKW1hbGxvYyhzaXplb2Yoc3RydWN0IHRub2RlKSk7Cgl5PVQtPm5pbDsgCgl4PVQtPnJvb3Q7Cgl3aGlsZSh4IT1ULT5uaWwpCgl7CgkJeT14OwoJCWlmKHotPmRhdGEgPCB4LT5kYXRhKQoJCXg9eC0+bGVmdENoaWxkOwoJCWVsc2UgCgkJeD14LT5yaWdodENoaWxkOwoJfQoJei0+cGFyZW50PXk7CglpZih5PT1ULT5uaWwpCglULT5yb290PXo7CgllbHNlIGlmICh6LT5kYXRhPCB5LT5kYXRhKQoJeS0+bGVmdENoaWxkPXo7CgllbHNlCgl5LT5yaWdodENoaWxkPXo7CgkKCXotPmxlZnRDaGlsZD1ULT5uaWw7Cgl6LT5yaWdodENoaWxkPVQtPm5pbDsKCXotPmNvbG9yPSdSJzsKCXJiaW5zZXJ0Zml4dXAoVCx6KTsKCQp9Cgp2b2lkIHZpc2l0KHN0cnVjdCB0bm9kZSogeCkKewoJaWYoeCE9TlVMTCkKCXsKCQl2aXNpdCh4LT5sZWZ0Q2hpbGQpOwoJCWlmKHgtPnBhcmVudCE9TlVMTCkKCQlwcmludGYoIiVkICVjICVkIFxuIiwgeC0+ZGF0YSwgeC0+Y29sb3IsIHgtPnBhcmVudC0+ZGF0YSk7CgkJZWxzZQoJCXByaW50ZigiJWQgJWMgTklMIFxuIiwgeC0+ZGF0YSwgeC0+Y29sb3IpOwoJCQkKCQkKCX0KfQp2b2lkIHByZV9maXhfdG91ciAoc3RydWN0IHRyZWUqIFQpCnsKCWlmKFQtPnJvb3Q9PU5VTEwpCglwcmludGYoImVtcHR5IHRyZWUiKTsKCWVsc2UKCXZpc2l0KFQtPnJvb3QpOwoJCn0KCgppbnQgbWFpbigpCnsKCWludCBhW109ezUsNCwxLDYsMTAsMTF9OwoJaW50IGk7CglzdHJ1Y3QgdG5vZGUqIG5vZGU7CglzdHJ1Y3QgdHJlZSAqdHJlZW47Cgl0cmVlbj0oc3RydWN0IHRyZWUqKW1hbGxvYyhzaXplb2Yoc3RydWN0IHRyZWUpKTsKCXRyZWVuLT5uaWw9TlVMTDsKCXRyZWVuLT5yb290PU5VTEw7Cglmb3IoaT0wO2k8NjtpKyspCgl7CgkJbm9kZT1jcmVhdGVub2RlKGFbaV0pOwoJCWluc2VydGlvbih0cmVlbiwgbm9kZSk7Cgl9CgkKcHJlX2ZpeF90b3VyKHRyZWVuKTsKCQoJcmV0dXJuIDA7CgkKCQoJCn0=