English edition note: The original title mentions recursion, stacks and queues, but the exercise below implements a binary search tree. Its deletion routine does not consistently repair parent pointers, so subsequent level-order traversal can use a stale or freed parent. Allocation failures are also unchecked. This historical example has not been presented as verified production code.

#About trees

Concept reference Data Structures: Stacks, Queues, Graphs and Trees
Binary tree reference Tree and binary tree concepts

#Data structures exercise: a block-by-block explanation

#📚 Problem

#Problem 1: Create and search a binary search tree

Store student records containing a student ID and a name in a binary search tree.
Use the student ID as the key.
Student IDs must be unique; a second insertion with a duplicate ID is ignored.
Implement functions that perform the following operations on the tree:

1. count all nodes;
2. count leaf nodes;
3. determine the tree height;
4. traverse the tree in level order, displaying each (parent)->[child] relationship;
5. traverse the tree in inorder;
6. search the tree;
7. delete a node;
8. delete the entire tree.

Using the supplied binary-search-tree structures and main() code, write a program that produces results like the example below.

//Supplied code and problem
typedef struct ELEMENT {
	int id_num;
	char name[10];
}element;

typedef struct TreeNode {
	element std;
	struct TreeNode* left, * right;
} TreeNode;

int main(void) {
	TreeNode* root = NULL; TreeNode* tmp = NULL; element item;
	item.id_num = 2021006; strcpy(item.name, "name6"); root = insert_node(root, item);
	item.id_num = 2021001; strcpy(item.name, "name1"); root = insert_node(root, item);
	item.id_num = 2021009; strcpy(item.name, "name9"); root = insert_node(root, item);
	item.id_num = 2021007; strcpy(item.name, "name7"); root = insert_node(root, item);
	item.id_num = 2021003; strcpy(item.name, "name3"); root = insert_node(root, item);
	item.id_num = 2021002; strcpy(item.name, "name2"); root = insert_node(root, item);
	item.id_num = 2021005; strcpy(item.name, "name5"); root = insert_node(root, item);
	item.id_num = 2021004; strcpy(item.name, "name4"); root = insert_node(root, item);
	item.id_num = 2021008; strcpy(item.name, "name8"); root = insert_node(root, item);
	item.id_num = 2021010; strcpy(item.name, "name10"); root = insert_node(root, item);
	printf("Count nodes and leaf nodes and calculate the binary search tree height\n");
	printf("Nodes = %d \nLeaf nodes = %d \nHeight = %d \n\n", get_node_count(root), get_leaf_count(root), get_height(root));
	printf("Binary search tree level-order traversal\n"); 
	level_order(root);

	printf("\n\n");
	printf("Binary search tree inorder traversal \n");
	inorder(root);

	printf("\n\nSearch the binary search tree for 2021010\n");
	tmp = search(root, 2021010);
	if (tmp != NULL)
		printf("Search succeeded: student ID %d, name %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("Student not found in the binary search tree \n");
	printf("\nDelete 2021006 from the binary search tree\n");
	delete_node(&root, 2021006);
	printf("\n\nSearch the binary search tree for 2021006\n");
	tmp = search(root, 2021006);
	if (tmp != NULL)
		printf("Search succeeded: student ID %d, name %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("Student not found in the binary search tree \n");

	printf("\n\nBinary search tree inorder traversal \n"); inorder(root);
	printf("\n\n");
	printf("\n\nDelete the entire binary search tree \n"); root = delete_tree(root);
	printf("\n\nBinary search tree level-order traversal\n"); level_order(root);
	printf("\n\n");

	return 0;
}

#Example output

Count nodes and leaf nodes and calculate the binary search tree height
Nodes = 10
Leaf nodes = 4
Height = 5

Binary search tree level-order traversal
Level 1 : [2021006]
Level 2 : (2021006)->[2021001] (2021006)->[2021009]
Level 3 : (2021001)->[2021003] (2021009)->[2021007] (2021009)->[2021010]
Level 4 : (2021003)->[2021002] (2021003)->[2021005] (2021007)->[2021008]
Level 5 : (2021005)->[2021004]


Binary search tree inorder traversal
[2021001] [2021002] [2021003] [2021004] [2021005] [2021006] [2021007] [2021008] [2021009] [2021010]

Search the binary search tree for 2021010
Search succeeded: student ID 2021010, name name10

Delete 2021006 from the binary search tree


Search the binary search tree for 2021006
Student not found in the binary search tree


Binary search tree inorder traversal
[2021001] [2021002] [2021003] [2021004] [2021005] [2021007] [2021008] [2021009] [2021010]



Delete the entire binary search tree
[2021002] [2021004] [2021005] [2021003] [2021001] [2021008] [2021010] [2021009] [2021007]

Binary search tree level-order traversal
The tree is empty.

#👨🏻‍💻 Solution code

This is probably not particularly clean code. I may find it poorly written when I revisit it, but I am keeping it here anyway.

The problem calls for the following functions:

#📝 Function pseudocode and implementation

#Complete code

//Binary tree example
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ELEMENT {
	int id_num;
	char name[10];
}element;

typedef struct TreeNode {
	element std;
	struct TreeNode* left, * right, * parent;
} TreeNode;

int max(int a, int b) {
	return (a > b) ? a : b;
}

TreeNode* new_node(element item) {
	TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
	newNode->std.id_num = item.id_num;
	strcpy(newNode->std.name, item.name);
	newNode->left = newNode->right = newNode->parent = NULL;
	return newNode;
}

TreeNode* insert_node(TreeNode* node, element item) {
    if (node == NULL) {
        TreeNode* newNode = new_node(item);
        return newNode;
    }
	if (item.id_num < node->std.id_num) {
		node->left = insert_node(node->left, item);
		node->left->parent = node;  // Set the parent node
	}
	else if (item.id_num > node->std.id_num) {
		node->right = insert_node(node->right, item);
		node->right->parent = node;  // Set the parent node
	}

    return node;
}

int get_node_count(TreeNode* node) {
	int count = 0;
	if (node != NULL) {
		count = 1 + get_node_count(node->left) + get_node_count(node->right);
	}
	return count;
}
int get_leaf_count(TreeNode* node) {
	int count = 0;
	if (node != NULL) {
		if (node->left == NULL && node->right == NULL) return 1;
		else {
			count = get_leaf_count(node->left) + get_leaf_count(node->right);
		}
	}
	return count;
}
int get_height(TreeNode* node) {
	int height = 0;
	if (node != NULL) {
		height = 1 + max(get_height(node->left), get_height(node->right));
	}
	return height;
}

void inorder(TreeNode* node) {
	if (node) {
		inorder(node->left);
		printf("[%d] ", node->std.id_num);
		inorder(node->right);
	}
}

TreeNode* search(TreeNode* node, int id_num) {
	if (node == NULL) return NULL;
	if (id_num == node->std.id_num) return node;
	else if (id_num < node->std.id_num)
		return search(node->left, id_num);
	else
		return search(node->right, id_num);

}

TreeNode* min_value_node(TreeNode* node) {
	TreeNode* current = node;

	while (current && current->left != NULL) {
		current = current->left;
	}
	return current;
}

void delete_node(TreeNode** rootRef, int id_num) {
	TreeNode* root = *rootRef;
	if (root == NULL) return;

	if (id_num < root->std.id_num)
		delete_node(&(root->left), id_num);
	else if (id_num > root->std.id_num)
		delete_node(&(root->right), id_num);
	else { // key is same
		if (root->left == NULL) {
			TreeNode* temp = root->right;
			free(root);
			*rootRef = temp;
		}
		else if (root->right == NULL) {
			TreeNode* temp = root->left;
			free(root);
			*rootRef = temp;
		}
		else {
			TreeNode* temp = min_value_node(root->right);
			root->std.id_num = temp->std.id_num;
			strcpy(root->std.name, temp->std.name);
			delete_node(&(root->right), temp->std.id_num);
		}
	}
}

TreeNode* delete_tree(TreeNode* root) {
	if (root == NULL) return NULL;

	root->left = delete_tree(root->left);
	root->right = delete_tree(root->right);
	printf("[%d] ",root->std.id_num);
	free(root);
	return NULL;
}

// Define a queue node
typedef struct QueueNode {
	TreeNode* treeNode;
	struct QueueNode* next;
} QueueNode;

// Define the queue
typedef struct {
	QueueNode* front;
	QueueNode* rear;
	int count;
} Queue;

// Initialize the queue
void initQueue(Queue* q) {
	q->front = q->rear = NULL;
	q->count = 0;
}

// Check whether the queue is empty
int isEmpty(Queue* q) {
	return q->count == 0;
}

// Add a node to the queue
void enqueue(Queue* q, TreeNode* node) {
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->treeNode = node;
	newNode->next = NULL;
	if (isEmpty(q)) {
		q->front = q->rear = newNode;
	}
	else {
		q->rear->next = newNode;
		q->rear = newNode;
	}
	q->count++;
}

// Remove a node from the queue
TreeNode* dequeue(Queue* q) {
	if (isEmpty(q)) return NULL;
	QueueNode* temp = q->front;
	TreeNode* result = temp->treeNode;
	q->front = q->front->next;
	if (q->front == NULL) q->rear = NULL;
	free(temp);
	q->count--;
	return result;
}

// Implement level-order traversal
void level_order(TreeNode* root) {
	if (root == NULL) {
		printf("The tree is empty.\n");
		return;
	}

	Queue q;
	initQueue(&q);
	enqueue(&q, root);

	int level = 0;

	while (!isEmpty(&q)) {
		int levelCount = q.count; // Number of nodes at the current level
		printf("Level %d : ", ++level);

		while (levelCount > 0) {
			TreeNode* current = dequeue(&q);

			// Print the current node
			if (current->parent != NULL) printf("(%d)->", current->parent->std.id_num);
			printf("[%d] ", current->std.id_num);

			if (current->left != NULL) enqueue(&q, current->left);
			if (current->right != NULL) enqueue(&q, current->right);

			levelCount--;
		}

		printf("\n");
	}
}

int main(void) {
	TreeNode* root = NULL; TreeNode* tmp = NULL; element item;
	item.id_num = 2021006; strcpy(item.name, "name6"); root = insert_node(root, item);
	item.id_num = 2021001; strcpy(item.name, "name1"); root = insert_node(root, item);
	item.id_num = 2021009; strcpy(item.name, "name9"); root = insert_node(root, item);
	item.id_num = 2021007; strcpy(item.name, "name7"); root = insert_node(root, item);
	item.id_num = 2021003; strcpy(item.name, "name3"); root = insert_node(root, item);
	item.id_num = 2021002; strcpy(item.name, "name2"); root = insert_node(root, item);
	item.id_num = 2021005; strcpy(item.name, "name5"); root = insert_node(root, item);
	item.id_num = 2021004; strcpy(item.name, "name4"); root = insert_node(root, item);
	item.id_num = 2021008; strcpy(item.name, "name8"); root = insert_node(root, item);
	item.id_num = 2021010; strcpy(item.name, "name10"); root = insert_node(root, item);
	printf("Count nodes and leaf nodes and calculate the binary search tree height\n");
	printf("Nodes = %d \nLeaf nodes = %d \nHeight = %d \n\n", get_node_count(root), get_leaf_count(root), get_height(root));
	printf("Binary search tree level-order traversal\n"); 
	level_order(root);
	
	printf("\n\n");
	printf("Binary search tree inorder traversal \n");
	inorder(root);

	printf("\n\nSearch the binary search tree for 2021010\n");
	tmp = search(root, 2021010);
	if (tmp != NULL)
		printf("Search succeeded: student ID %d, name %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("Student not found in the binary search tree \n");
	printf("\nDelete 2021006 from the binary search tree\n");
	delete_node(&root, 2021006);
	printf("\n\nSearch the binary search tree for 2021006\n");
	tmp = search(root, 2021006);
	if (tmp != NULL)
		printf("Search succeeded: student ID %d, name %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("Student not found in the binary search tree \n");

	printf("\n\nBinary search tree inorder traversal \n"); inorder(root);
	printf("\n\n");
	printf("\n\nDelete the entire binary search tree \n"); root = delete_tree(root);
	printf("\n\nBinary search tree level-order traversal\n"); level_order(root);
	printf("\n\n");

	return 0;
}