#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <math.h>

#include "libbst.h"

/* print with pre-order traversal */
void bst_porder_print( bst_ptr root, int depth, int* pos, char** buf ){

	char tmp[4];
	
	if( root == NULL )
		return;

	/* traversal left child first */
	if( root->left != NULL )
		bst_porder_print( root->left, depth+1, pos, buf );
	
	/* traversal current node */
	sprintf( tmp, "%3d", root->var );
	
	buf[depth][*pos] = tmp[0];
	buf[depth][(*pos)+1] = tmp[1];
	buf[depth][(*pos)+2] = tmp[2];
	
	(*pos) += 3;
	
	/* traversal right child last */
	if( root->right != NULL )
		bst_porder_print( root->right, depth+1, pos, buf );
	
}

/* remove white spaces in right side of buf */
void bst_rtrim( char* str ){

	int i = strlen(str);
	
	while( str[--i] == ' ' && i > 0 );
	str[i+1] = 0;

}

/* print */
void bst_print( bst_ptr root, FILE* out ){

	int level;
	int i, size;

	char** buf;
	
	level = bst_get_level( root );

	/* if tree is empty, then return; */
	if( level < 1 )
		return;
	
	/* allocate buffer */
	buf = (char**)malloc( sizeof(char*)*level );
	size = sizeof(char) * 3 * ( pow(2,level) -1 );
	
	for( i = 0 ; i < level ; i++ ){
		buf[i] = (char*)malloc(size);
		memset( buf[i], ' ', size );
	}

	i = 0;
	bst_porder_print( root, 0, &i,  buf );
	
	for( i = 0 ; i < level ; i++ ){
		bst_rtrim( buf[i] );
		fprintf( stdout, "%s\n", buf[i] );
		free(buf[i]);
	}
	free(buf);

}