#include <stdio.h>
#include <stdlib.h>
#include <deque>
using namespace std;



struct TreeStruct {
	int v;

	/* Left, right and parent pointers */
	struct TreeStruct *l, *r, *p; 
	bool visit;
};
typedef struct TreeStruct Tree;



/* Creates a new tree with root v */
Tree *tree_new( int v ) {
	Tree *t = (Tree *) malloc( sizeof(Tree) );
	t->v = v;
	t->l = NULL;
	t->r = NULL;
	t->p = NULL;
	t->visit = 0;
	return t;
}


/* Inserts an element into a tree */
void tree_insert( Tree *t, int v ) {
	
	Tree *p = NULL;
	
	while (t != NULL) {
		p = t;
		if (v < t->v) 
			t = t->l;
		else if (v > t->v) 
			t = t->r;
		else
			return;
	}
	
	t = tree_new( v );


	if (v < p->v) 
		p->l = t;
	else
		p->r = t;

	t->p = p;
}

/* Look for an element on the tree */
Tree * tree_find( Tree *t, int v ) {
	
	while (t != NULL) {
		if (v < t->v) 
			t = t->l;
		else if (v > t->v)
			t = t->r;
		else
			return t;
	}
	return NULL;

}

/* In/pre/post/level order walks */
void tree_walk_inorder_rec( Tree *t ) {
	if (t != NULL) {
		tree_walk_inorder_rec( t->l );
		printf( "%d ", t->v );
		tree_walk_inorder_rec( t->r );
	}
}

// Using a stack
void tree_walk_inorder( Tree *t ) {
	deque<Tree *> S;
	Tree *el;
	if (t == NULL) return;

	S.push_front( t );

	while (S.size()) {
		el = S.front();
		S.pop_front();
		
		
		if (el->r) 
			S.push_front( el->r );

		if (el->l && !el->l->visit) {
			S.push_front( el );
			S.push_front( el->l );
		} else if (!el->visit){
			printf( "%d ", el->v );
			el->visit = 1;
		}

	}
}

// Using parent pointers
void tree_walk_inorder2( Tree *t ) {
	
	Tree *cur, *prev, *next;

	cur = t;
	prev= NULL;
	while ( cur ) {


		// Going down
		if (prev==NULL || prev == cur->p ) {
			if (cur->l)
				next = cur->l;
			else { 
				printf( "%d ", cur->v );
				if (cur->r) 
					next = cur->r;
				else 
					next = cur->p;
			}

		// From left child to parent
		} else if ( prev == cur->l ) {
			printf( "%d ", cur->v );
			if (cur->r)
				next = cur->r;
			else
				next = cur->p;

		// From right child to parent
		} else if ( prev == cur->r ) {
			next = cur->p;
		}
		
		prev = cur;
		cur = next;

	}

}


void tree_walk_postorder_rec( Tree *t ) {
	if (t != NULL) {
		tree_walk_postorder_rec( t->l );
		tree_walk_postorder_rec( t->r );
		printf( "%d ", t->v );
	}
}

void tree_walk_postorder( Tree *t ) {
	if (t == NULL)
		return;

	Tree *cur, *prev, *next;
	
	cur = t;
	prev = NULL;
	while ( cur ) {
		
		if (prev == NULL || prev == cur->p) {
			if (cur->l) 
				next = cur->l;
			else if (cur->r)
				next = cur->r;
			else {
				printf( "%d ", cur->v );
				next = cur->p;
			}
		} else if (prev == cur->l) {
			if (cur->r)
				next = cur->r;
			else {
				printf( "%d ", cur->v );
				next = cur->p;
			}

		} else if (prev == cur->r) {
			next = cur->p;
			printf( "%d ", cur->v );
		}
		prev = cur;
		cur = next;
	}

}

void tree_walk_preorder_rec( Tree *t ) {
	if (t != NULL) {
		printf( "%d ", t->v );
		tree_walk_preorder_rec( t->l );
		tree_walk_preorder_rec( t->r );
	}
}

void tree_walk_preorder( Tree *t ) {
	if (t == NULL) return;

	deque<Tree *> S;
	Tree *el;

	S.push_front( t );

	while (S.size()) {
		el = S.front();
		S.pop_front();

		printf( "%d ", el->v );

		if (el->r) S.push_front( el->r );
		if (el->l) S.push_front( el->l );
	}
}

void tree_walk_preorder2( Tree *t ) {
	if (t==NULL) return;

	Tree *prev, *cur, *next;

	cur = t;
	prev = NULL;

	while (cur) {
		
		if (prev == NULL || prev == cur->p) {
			printf( "%d ", cur->v );

			if (cur->l) next = cur->l;
			else if (cur->r) next = cur->r;
			else next = cur->p;

			
		} else if (prev == cur->l) {
			if (cur->r) next = cur->r;
			else next = cur->p;
		} else {
			next = cur->p;
		}
	
		prev = cur;
		cur = next;
	}

}

void tree_walk_level( Tree *t ) {
	deque<Tree *> Q;
	Tree *el;

	if (t == NULL) return;

	Q.push_back( t );

	int level = 1;
	while (Q.size()) {
		el = Q.front();
		Q.pop_front();
	
		printf( "%d ", el->v );
		if (el->l) Q.push_back( el->l );
		if (el->r) Q.push_back( el->r );

	}
}




int main( void ) {
	int values[] = {3,4,5,1,2,10,20,12,7,-12,23};
	int nvalues = 11;

	/* Insert values into tree */
	printf( "[] Inserting values: %d", values[0] );
	Tree *t = tree_new( values[0] );
	int i;
	for (i=1; i < nvalues; i++) {
		tree_insert( t, values[i] );
		printf( "%d ", values[i] );
	}
	printf( "\n\n" );


	/* Check all values */
	printf( "[] Checking for values: " );
	for (i=0; i < nvalues; i++) {
		if (tree_find( t, values[i] )) 
			printf( "%d ", values[i] );
		else
			printf( "[error; can't find %d] ", values[i] );
	}
	printf( "\n\n" );


	/* Walks */
	printf( "[] Inorder walk (recursive):\t" );
	tree_walk_inorder_rec( t );
	printf( "\n" );
	printf( "[] Inorder walk (iterative):\t" );
	tree_walk_inorder( t );
	printf( "\n" );
	printf( "[] Inorder walk (iterative2):\t" );
	tree_walk_inorder2( t );
	printf( "\n\n" );
	

	printf( "[] Postorder walk (recursive):\t" );
	tree_walk_postorder_rec( t );
	printf( "\n" );
	printf( "[] Postorder walk (iterative):\t" );
	tree_walk_postorder( t );
	printf( "\n\n" );
	


	printf( "[] Preorder walk (recursive):\t" );
	tree_walk_preorder_rec( t );
	printf( "\n" );
	printf( "[] Preorder walk (iterative):\t" );
	tree_walk_preorder( t );
	printf( "\n" );
	printf( "[] Preorder walk (iterative2):\t" );
	tree_walk_preorder2( t );
	printf( "\n\n" );



	printf( "[] Level walk: " );
	tree_walk_level( t );
	printf( "\n" );


	return 0;
}