#include <stdio.h>
#include <math.h>

struct node {
	int element;
	struct node* left;
	struct node* right;
};


int lookup ( struct node* _node_ptr, int target_element )
{
	if ( NULL == _node_ptr ) return ( 0 );
	if ( target_element == _node_ptr -> element ) 
return ( 1 );
	else {
		if ( target_element < _node_ptr -> 
element ) return ( lookup ( _node_ptr -> left, 
target_element ) );
		else return ( lookup ( _node_ptr -> right, 
target_element ) );
	}
}

int max_depth ( struct node* _node_ptr )
{
	if ( NULL == _node_ptr ) return ( 0 );
	else {
		int _l_depth =  max_depth ( _node_ptr -> 
left );
		int _r_depth =  max_depth ( _node_ptr -> 
right );
		return ( ( _l_depth > _r_depth ) ? ( 
_l_depth + 1 ) : ( _r_depth + 1 ) );
	}
}

struct node* create_node ( int _element )
{
	struct node* _node = ( struct node* ) malloc ( 
sizeof (struct node) );
	_node -> element = _element;
	_node -> left = NULL;
	_node -> right = NULL;

	return ( _node );
}

struct node* insert ( struct node* _node_ptr, int _element )
{
	if ( NULL== _node_ptr ) return ( create_node ( 
_element ) );
	else {
		if ( _element <= _node_ptr -> element ) 
_node_ptr -> left = ( insert ( _node_ptr -> left, 
_element ) );
		else _node_ptr -> right = ( insert ( 
_node_ptr -> right, _element ) );
	}
	return ( _node_ptr );
}

void inorder_traversal ( struct node* _node_ptr )
{
	if ( NULL == _node_ptr ) return;
	inorder_traversal ( _node_ptr -> left );
	printf ("\n The element :%d", _node_ptr -> 
element );
	inorder_traversal ( _node_ptr -> right );
}

void preorder_traversal ( struct node* _node_ptr )
{
	if ( NULL == _node_ptr ) return;
	printf ("\n The element :%d", _node_ptr -> 
element );
	preorder_traversal ( _node_ptr -> left );
	preorder_traversal ( _node_ptr -> right );
}

void postorder_traversal ( struct node* _node_ptr )
{
	if ( NULL == _node_ptr ) return;
	postorder_traversal ( _node_ptr -> left );
	postorder_traversal ( _node_ptr -> right );
	printf ("\n The element :%d", _node_ptr -> 
element );
}


int main ( int argc, char* argv[] )
{
	int* array_int, nTotalCount = 10, i;
	struct node* _node_ptr = NULL;
	int temp = 0;

	printf ( "\n/********************** Binary Tree 
********************/" );
	array_int = ( int* ) malloc ( nTotalCount * sizeof 
( int ) );

	for ( i = 0; i < nTotalCount; i++ )
	{
		temp = rand() % 100 ;
		array_int [i] =  ( temp == 0 ) ? ( temp + 
1 ) : temp;
	}

	printf( "\nThe Numbers in given order" );
	for ( i = 0; i < nTotalCount; i++ )
		printf ( "\t%d", array_int [i] );

	for ( i = 0; i < nTotalCount; i++ )
		_node_ptr = insert ( _node_ptr, array_int 
[i] );

	inorder_traversal ( _node_ptr );
	printf ("\n max possible nodes :%f", pow ( 2, 
max_depth ( _node_ptr ) ) );

	free ( array_int [i] );
}