Generates a random tree, then searches for a node

search.c

   /*
	* Generates a random tree, then searches for a node
	*
	* Compile w GCC then run:
	*	> gcc search.c -o search
	*	> ./search
	*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 		/* needed for rand() */

#define MAXBRANCHES 3
#define MAXNODES 26		/* only lowercase alphabet */

typedef struct node{
	int val; // contents of the node
	char name; // name of node
	
	// each node can have up to 3 branches
	struct node *branch[MAXBRANCHES];
} node_t;

// private func declarations
int generate( node_t** root );
node_t* search_df( node_t* root, char targetname );
node_t* search_breadth( node_t* root, char targetname );
void delete( node_t* root );

// public function defines
int main(void) {
	node_t *root = NULL;
	node_t *found = NULL;
	int treenodes;
	char searchkey;

	// Initialize node tree
	treenodes = generate(&root);
	if(treenodes == -1) {
		printf("\nERROR: couldn't init tree.\n");
		return 0;
	}
	printf("\nThe list contains %d values.\n", treenodes );

	// Search for entered node
	printf("\nEnter node to search for: ");
	scanf("%c", &searchkey);
	found = search_df( root, searchkey );
	found = search_breadth( root, searchkey );
	if(found == NULL) {
		printf("\nNULL: Couldn't find node.\n");
	} else {
		printf("\nNode '%c' contains value: %d.\n", searchkey, found->val);
	}

	// Cleanup & terminate process
	delete(root);
	return 0;
}

// private function defines
node_t* allocate_node( node_t** address, int* nodecount ) {
	node_t* temp = malloc(sizeof(node_t));
	if(temp == NULL) {
		printf("ERROR: Couldn't allocate memory.\n");
		return NULL; // ERROR
	}
	*address = temp;
	temp->val = rand() % 255; // random content
	temp->name = *nodecount + 0x61; // lower-case ascii
	(*nodecount)++; // increase node count
	return *address;
}

int generate( node_t** root ) {
	int nodecount = 0; // how many nodes created
	// node_t* temp;
	node_t* top;
	node_t* stack[MAXNODES]; // array used as stack
	int stacksize = 0; // num pointers on stack
	time_t t; // for rand()
	srand((unsigned) time(&t)); // seed rand()
	
	// malloc root
	top = allocate_node( root, &nodecount );
	// special case where all 3 branches must be allocated
	for(int i=0; i<MAXBRANCHES; i++) {
		stack[++stacksize] = allocate_node( &(top->branch[i]), &nodecount );
	}

	// probabilistically assign & malloc branches
	while(stacksize) {
		top = stack[stacksize--];
		for(int i=0; i<MAXBRANCHES; i++) {
			top->branch[i] = NULL; // init to NULL
			if( !(rand() % 4) && (nodecount < MAXNODES) ) { // 25% chance
				stack[++stacksize] = allocate_node( &(top->branch[i]), &nodecount );
			}
		}
	}
	return nodecount; // total nodes created
}

node_t* search_df( node_t* root, char targetname ) {
	// depth-first search
	node_t* found = NULL;
	node_t* temp;
	node_t* stack[MAXNODES]; // array used as stack
	int stacksize = 0; // how many addresses on stack
	int moves = 0;

	stack[++stacksize] = root;
	
	while(stacksize) {
		moves++; // took another move
		temp = stack[stacksize--];

		if(temp->name == targetname ) { // node is the target
			found = temp;
			printf("\nDF: Found in %d move(s).\n", moves);
			return found; // early exit!
		} else { // node exists, but isn't the answer
			for(int i=0; i<MAXBRANCHES; i++) { // check all potential branches
				if(temp->branch[i] != NULL) { // node exists
					stack[++stacksize] = temp->branch[i]; // push to stack
				}
			}
		}
	}
	return found; // NULL pointer
}

node_t* search_breadth( node_t* root, char targetname ){
	//breadth-first search
	node_t* found = NULL;
	node_t* temp;
	node_t* queue[MAXNODES];
	int q_start = 0;
	int q_count = 1;
	int moves = 0;

	queue[0] = root;

	while(q_count) {
		moves++;
		temp = queue[q_start++];
		q_count--;

		if(temp->name == targetname ) { // node is the target
			found = temp;
			printf("\nBF: Found in %d move(s).\n", moves);
			return found; // early exit!
		} else {
			for(int i=0; i<MAXBRANCHES; i++) {
				if(temp->branch[i] != NULL) {
					queue[q_start + (q_count++)] = temp->branch[i];
				}
			}
		}
	}
	return found; // NULL
}

void delete( node_t* root ) {
	node_t* temp;
	node_t* stack[MAXNODES]; // array used as stack
	int stacksize = 0; // stack size

	// push root to stack
	stack[++stacksize] = root;

	while(stacksize) {
		temp = stack[stacksize--]; // pop from stack
		if(temp != NULL) { // check if node exists
			// push branches
			for(int i=0; i<MAXBRANCHES; i++) {
				stack[++stacksize] = (temp->branch[i]);
			}
			// free popped node
			free(temp);
		}
	}
	return;
}