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

#include "tree.h"

/* Internal tree node object */
struct treeNode {
  char *val;
  struct treeNode *left;
  struct treeNode *right;
};

/* Representation of tree object */
struct tree_t {
  struct treeNode *root;
};

struct tree_t *new_tree() {
  struct tree_t *tree = malloc(sizeof(struct tree_t));
  tree->root = NULL;
  return tree;
}

struct treeNode *treeInsert_aux(struct treeNode *T, char *str) {
  int dir;
  if (T == NULL) {
    T = malloc(sizeof(struct treeNode));
    T->val   = strcpy(malloc(strlen(str)+1), str);
    T->left  = NULL;
    T->right = NULL;
  } else {
    dir = strcmp(str, T->val);
    if (dir < 0) T->left  = treeInsert_aux(T->left, str);
    else if (dir > 0) T->right = treeInsert_aux(T->right, str);
  }
  return T;  
}

void treeInsert(struct tree_t *tree, char *str) {
  tree->root = treeInsert_aux(tree->root, str);
}

void treePrint_aux(struct treeNode *T, int depth) {
  int i;
  if (T) {
    treePrint_aux(T->left, depth+1);
    for (i=0; i<depth-1; i++) printf("|  ");
    if (depth > 0) printf("|");
    printf("-%s\n", T->val);
    treePrint_aux(T->right, depth+1);
  }
}

void treePrint(struct tree_t *tree) {
  treePrint_aux(tree->root, 0);
}

void treeRemove(struct tree_t *tree, char *str) {
  /* Write this routine and its support */
}