level order traversal in BST

level-order.c

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

typedef struct Node {
	int key;
	struct Node *left, *right;
} Node;

Node* newNode(int key) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->key = key;
	node->left = node->right = NULL;
	return node;
}

Node* insert(Node* root, int key) {
	if (root == NULL) return newNode(key);
	if (key < root->key)
		root->left = insert(root->left, key);
	else
		root->right = insert(root->right, key);
	return root;
}

Node* minValueNode(Node* node) {
	Node* current = node;
	while (current && current->left != NULL)
		current = current->left;
	return current;
}

Node* deleteNode(Node* root, int key) {
	if (root == NULL) return root;
	if (key < root->key)
		root->left = deleteNode(root->left, key);
	else if (key > root->key)
		root->right = deleteNode(root->right, key);
	else {
		if (root->left == NULL) {
			Node* temp = root->right;
			free(root);
			return temp;
		} else if (root->right == NULL) {
			Node* temp = root->left;
			free(root);
			return temp;
		}
		Node* temp = minValueNode(root->right);
		root->key = temp->key;
		root->right = deleteNode(root->right, temp->key);
	}
	return root;
}

typedef struct {
	Node* data[100];
	int front, rear;
} Queue;

void enqueue(Queue* q, Node* node) {
	q->data[q->rear++] = node;
}
Node* dequeue(Queue* q) {
	return q->data[q->front++];
}
int isEmpty(Queue* q) {
	return q->front == q->rear;
}

void levelOrder(Node* root) {
	if (root == NULL) return;
	Queue q;
	q.front = q.rear = 0;
	enqueue(&q, root);
	while (!isEmpty(&q)) {
		Node* temp = dequeue(&q);
		printf("%d ", temp->key);
		if (temp->left) enqueue(&q, temp->left);
		if (temp->right) enqueue(&q, temp->right);
	}
	printf("\n");
}

int main() {
	int n;
	scanf("%d", &n);

	Node* root = NULL;
	for(int i=0; i<n; i++){
		int d;
		scanf(" %d", &d);
		root = insert(root, d);
	}
	printf("Initial BST: ");
	levelOrder(root);
	int val;
	scanf("%d", &val);
	root = insert(root, val);
	printf("BST after inserting a new node: ");
	levelOrder(root);
	scanf("%d", &val);
	root = deleteNode(root, val);
	printf("BST after deleting node : ");
	levelOrder(root);

	return 0;
}