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

void tree_insert(tree *T, etree *z)
{
    etree 
	*y = (etree *) 0, 
	*x = T -> root;
    while (x != (etree*) 0) {
	y = x;
	if (strcmp(z -> key, x -> key) < 0) x = x -> left;
	else x = x -> right;
    }
    z -> parent = y;
    if (y == (etree*) 0) T -> root = z;
    else if (strcmp(z -> key, y -> key) < 0) y -> left = z;
    else y -> right = z; 
}

etree *tree_search(etree *x, const char *k) 
{
    while ((x != (etree*) 0) && (strcmp(k, x -> key) != 0)) {
	if (strcmp(k, x -> key) < 0) x = x -> left;
	else x = x -> right;
    }
    return x;
}



void process_string(tree *T, const char *buf)
{
    etree *x = tree_search(T -> root, buf);
    if (x != (etree*) 0) x -> count ++;
    else {
	x = (etree*) malloc(sizeof(etree));
	x -> count = 1;
	x -> key = (char*) malloc((1 + strlen(buf)) * sizeof(char));
	strcpy(x -> key, buf);
	x -> left = x -> right = x -> parent = (etree*) 0;
	tree_insert(T, x);
    }
}

void inorder_tree_walk(etree *x)
{
    if (x != (etree*) 0) {
	inorder_tree_walk(x -> left);
	printf("%7d %s\n", x -> count, x -> key);
	inorder_tree_walk(x -> right);
    }
}