Counting Nodes at each Level in BST
Understanding how to count and display nodes at each level.
The logic to display nodes at each level, count the number of nodes at each level, and determine the total number of levels in a Binary Search Tree (BST) involves level-order traversal (also known as Breadth-First Search (BFS).
Level-Order Traversal (BFS)
Level-order traversal processes nodes level by level, starting from the root node and moving down to the deepest level. This is achieved using a queue data structure.
Steps for Level-Order Traversal:
Start with the root node and enqueue it.
While the queue is not empty:
Dequeue a node from the front of the queue.
Process the node (e.g., print its value).
Enqueue its left child (if it exists).
Enqueue its right child (if it exists).
Repeat until the queue is empty.
Display Nodes at Each Level
To display nodes at each level, we need to process nodes level by level. This requires keeping track of the number of nodes at the current level.
Steps to Display Nodes at Each Level:
Initialize a queue and enqueue the root node.
While the queue is not empty:
Determine the number of nodes at the current level (
nodeCount = rear - front).Process all nodes at the current level:
Dequeue a node and print its value.
Enqueue its left and right children (if they exist).
Print the count of nodes at the current level.
Move to the next level.
Count Nodes at Each Level
The number of nodes at each level is determined by the number of nodes processed in the current iteration of the level-order traversal.
Steps to Count Nodes at Each Level:
Use the same level-order traversal approach.
For each level, count the number of nodes dequeued (
nodeCount).Print the count after processing all nodes at the current level.
Count Total Levels in the Tree
The total number of levels in the tree is equal to the number of times the level-order traversal processes a new level.
Steps to Count Total Levels:
Use the same level-order traversal approach.
Initialize a counter (
levels) to keep track of the number of levels.For each level processed, increment the
levelscounter.Return the
levelscounter as the total number of levels.
C program
C program that uses a Binary Search Tree (BST) Library to:
Display nodes at each level.
Count the number of nodes at each level.
Display the total number of levels in the tree.
The program is modularized into a BST library (bst.h and bst.c) and a main program (main.c).
BST Library (bst_count_level.h
bst_count_level.h (Header File)
This file declares the structure and functions for the BST library.
#ifndef BST_H #define BST_H // Define the structure for a BST node struct Node { int data; struct Node* left; struct Node* right; }; // Function prototypes struct Node* createNode(int data); struct Node* insert(struct Node* root, int data); void printLevelNodes(struct Node* root); int countLevels(struct Node* root); #endif
BST Library (bst_count_level.c
bst_count_level.c (Source File)
This file implements the functions declared in bst.h.
#include "bst_count_level.h" #include <stdlib.h> #include <stdio.h> // Function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } // Function to insert a node into the BST struct Node* insert(struct Node* root, int data) { if (root == NULL) { return createNode(data); } if (data < root->data) { root->left = insert(root->left, data); } else if (data > root->data) { root->right = insert(root->right, data); } return root; } // Function to print nodes at each level and count nodes at each level void printLevelNodes(struct Node* root) { if (root == NULL) { return; } // Create a queue for level-order traversal struct Node* queue[100]; int front = 0, rear = 0; queue[rear++] = root; int level = 0; while (front < rear) { int nodeCount = rear - front; printf("Level %d: ", level); printf("Nodes: "); // Process all nodes at the current level for (int i = 0; i < nodeCount; i++) { struct Node* current = queue[front++]; printf("%d ", current->data); // Enqueue left child if (current->left != NULL) { queue[rear++] = current->left; } // Enqueue right child if (current->right != NULL) { queue[rear++] = current->right; } } printf(" | Count: %d\n", nodeCount); level++; } } // Function to count the total number of levels in the BST int countLevels(struct Node* root) { if (root == NULL) { return 0; } // Create a queue for level-order traversal struct Node* queue[100]; int front = 0, rear = 0; queue[rear++] = root; int levels = 0; while (front < rear) { int nodeCount = rear - front; // Process all nodes at the current level for (int i = 0; i < nodeCount; i++) { struct Node* current = queue[front++]; // Enqueue left child if (current->left != NULL) { queue[rear++] = current->left; } // Enqueue right child if (current->right != NULL) { queue[rear++] = current->right; } } levels++; } return levels; }
Main Program (bst_count_level_nodes.c)
This file uses the BST library to create a BST, insert nodes, and display nodes at each level, count nodes at each level, and display the total number of levels.
#include <stdio.h> #include "bst_count_level.h" int main() { struct Node* root = NULL; // Insert nodes into the BST root = insert(root, 50); root = insert(root, 30); root = insert(root, 20); root = insert(root, 40); root = insert(root, 70); root = insert(root, 60); root = insert(root, 80); // Display nodes at each level and count of nodes at each level printf("Nodes at each level:\n"); printLevelNodes(root); // Count and display the total number of levels in the BST int totalLevels = countLevels(root); printf("Total levels in the BST: %d\n", totalLevels); return 0; }
