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

#define max(a,b) ((a>b)?a:b)

typedef struct _tree{
  int key;
  int ht;
  struct _tree *l;
  struct _tree *r;
}tree;

typedef tree *bst;


bst create_node(int x){
  bst t = (bst)malloc(sizeof(tree));
  t->key = x;
  t->ht = 0;
  t->l = NULL;
  t->r = NULL;
  return t;
}

bst insert(bst T, int x){
  bst new = create_node(x);
  
  if(T == NULL)
    return new;

  bst t = T;
  while(1){
    if(t->key < x){
      if(t->r == NULL){
	t->r = new;
	break;
      }
      else
	t = t->r;
    }
    else if(t->key > x){
      if(t->l == NULL){
	t->l = new;
	break;
      }
      else
	t = t->l;
    }
    else
      break;
    }
  return T;
}

void preorder(bst T){
  if(T == NULL)
    return;
  printf("%d ", T->key);
  preorder(T->l);
  preorder(T->r);
}

void inorder(bst T){
  if(T == NULL)
    return;
  inorder(T->l);
  printf("%d ", T->key);
  inorder(T->r);
}

void print_tree(bst T){
  printf("   Preorder: ");
  preorder(T);
  printf("\n   Inorder: ");
  inorder(T);
  printf("\n");
}

int height(bst T){
  if(T == NULL)
    return 0;
  if(T->r == NULL && T->l == NULL){
    return 0;
  }
  T->ht = 1+max(height(T->l),height(T->r));
  return T->ht;
}

void print_hrange(bst T, int k, int l){
  if(T == NULL)
    return;
  print_hrange(T->l,k,l);
  if(T->ht >= k && T->ht <=l){
    printf("(%d:%d)  ", T->key,T->ht);
  }
  print_hrange(T->r,k,l);
}

int main(){
  bst T = NULL;

  int n, i, x;
  printf("n = ");
  scanf("%d", &n);

  printf("\nEnter keys to insert\n   ");
  for(i=0; i<n; i++){
    scanf("%d", &x);
    T = insert(T,x);
  }

  printf("\nTraversals of the created binary search tree.\n");
  print_tree(T);

  height(T);
  printf("\nMaximum height: %d\n\n",T->ht);

  int k,l;
  printf("k = "); scanf("%d", &k);
  printf("l = "); scanf("%d", &l);
  printf("key:height for all nodes in the height range [%d:%d]\n   ",k,l);
  print_hrange(T,k,l);
  printf("\n");
  
  return 0;
}