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

typedef struct NodeType *Node;
struct NodeType {
    int value;
	Node left;
	Node right;
};

Node nodeInit(int v) {
	Node n = malloc(sizeof(struct NodeType));
	n->value = v;
	n->left = NULL;
	n->right = NULL;
	return n;
}

Node nodeAdd(Node n, int v) {
	if (n == NULL) {
		return nodeInit(v);
	} else {
		if (v < n->value) {
			n->left = nodeAdd(n->left, v);
		} else {
			n->right = nodeAdd(n->right, v);
		}
		return n;
	}
}

void nodeAdd2(Node *n, int v) {
	if (*n == NULL) {
		*n = nodeInit(v);
	} else {
		if (v < (*n)->value) {
			nodeAdd2(&(*n)->left, v);
		} else {
			nodeAdd2(&(*n)->right, v);
		}
	}
}

void nodeDump(Node n, int c) {
	int i;
	if (n == NULL) {
		return;
	}
	nodeDump(n->right, c + 1);
	for (i = 0; i < c; i++) {
		printf(" ");
	}
	printf("%d\n", n->value);
	nodeDump(n->left, c + 1);
}

int main(void) {
	int i;
	int c = 10000;
	clock_t start;
	clock_t end;
	Node n1;
	Node n2;
	
	start = clock();
	n1 = NULL;
	for (i = 0; i < c; i++) {
		n1 = nodeAdd(n1, i);
	}
	end = clock();
	printf("nodeAdd1 : %f\n", (double)end - start);

	start = clock();
	n2 = NULL;
	for (i = 0; i < c; i++) {
		nodeAdd2(&n2, i);
	}
	end = clock();
	printf("nodeAdd2 : %f\n", (double)end - start);

	return EXIT_SUCCESS;
}