#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
 
#define SIZE 50
 
typedef struct node *link;
 
struct node {
	int item;
	struct node *link[2];
};
 
link make_node(int data)
{
	link x = (link)malloc(sizeof *x);
	x->item = data;
	x->link[0] = NULL; x->link[1] = NULL;
	return x;
}
 
link make_tree(link root, int data)
{
	if (root == NULL)
		root = make_node(data);
	if (root->item == data)
		return root;
	else
	{
		int dir = root->item < data;
		root->link[dir] = make_tree(root->link[dir], data);
	}
	return root;
}
 
void disp_tree(link tree, int level)
{
	int i;
 
  if ( tree == NULL ) {
    for ( i = 0; i < level; i++ )
      printf ( "\t" );
    printf ( "~\n" );
 
    return;
  }
 
	disp_tree ( tree->link[1], level + 1 );
 
  for ( i = 0; i < level; i++ )
    printf ( "\t" );
  printf ( "%d\n", tree->item );
 
	disp_tree ( tree->link[0], level + 1 );
}
 
/*
static int N, head, tail;
struct node *q[50];
 
void put(link item) 
{
	q[tail++] = item;
	tail = tail % N;
}
 
link get() 
{
	head = head % N;
	return q[head++];
}
*/
// preorder
void preorder(link root, int a[])
{
	while (*a != 0)
	{
		make_tree(root, *a);
		a++;
	}
 
	disp_tree(root, 1);
}
// inorder
void inorder()
{}
 
int main(void) 
{
	int num;
	puts("1: Preorder Traversal");
	puts("2: Inorder Traversal");
	puts("Enter your choice:");
	scanf("%d", &num);
	fflush(stdin);
 
	int i = 0, j = 0, val[SIZE] = {0};
	char trav[SIZE];
	puts("Enter the traversal order");
	fgets(trav, SIZE, stdin);
	while (isdigit(trav[i]))
	{
		val[j++] = 10*val[i] + (trav[i++]-'0');		
		while (trav[i] == ' ') 
			i++;
	}
 
	if (num == 1) 
	{
		link root = make_node(val[0]);
		preorder(root, val);
	}
	else 
		inorder();
 
	return 0;
}