DSA-II | DSA-II Lab | Python | TOC | Data Analytics-Lab | Networking | NET/SET | Data Science

Binary Search Tree (BST) in C : To Count nodes

 Assignment 1. Set A a) SPPU: 

Write a program in which uses binary search tree library and counts the total nodes and total nodes in the tree. int count(T) returns the total number of nodes from BST. int countLeaf(T) returns the total number of leaf nodes from BST.  gien source vertex using adjacency cost matrix.

            This experiment demonstrates the implementation of a Binary Search Tree (BST) in C and includes functions to count:

  1. Total number of nodes in the tree.

  2. Total number of leaf nodes in the tree.

The program uses recursive traversal to count the nodes and leaf nodes. It is designed to help students understand how BSTs work, how to traverse them, and how to perform basic operations like counting nodes.

Logic Used to Count Nodes

1. Counting Total Nodes

  • Logic: Every node in the tree contributes to the total count. The total number of nodes is the sum of:

    • The current node (1).

    • The number of nodes in the left subtree.

    • The number of nodes in the right subtree.

  • Recursive Approach:

    • If the current node is NULL, return 0 (base case).

    • Otherwise, return 1 + count(left subtree) + count(right subtree).

2. Counting Leaf Nodes

  • Logic: A leaf node is a node that has no children (both left and right pointers are NULL). The total number of leaf nodes is the sum of:

    • Leaf nodes in the left subtree.

    • Leaf nodes in the right subtree.

  • Recursive Approach:

    • If the current node is NULL, return 0 (base case).

    • If the current node is a leaf (both left and right are NULL), return 1.

    • Otherwise, return countLeaf(left subtree) + countLeaf(right subtree).

Create BST Library.

              To create a Binary Search Tree (BST) library in C, we need to modularize the code into a header file (bst_countNode.h) and a source file (bst_countNodes.c). The library will provide functions for creating, inserting, and counting nodes in the BST. The main program will then use this library to perform operations.

Below is the implementation:

1. BST Library (bst_countNodes.h and bst_countNodes.c)

 

bst_countNodes.h (Header File)

This file declares the structure and functions for the BST library.

download code
 
#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);
int count(struct Node* root);
int countLeaf(struct Node* root);

#endif

bst_countNodes.c (Source File)

This file implements the functions declared in bst.h.

download code 

#include "bst_countNodes.h"
#include <stdlib.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 count the total number of nodes in the BST
int count(struct Node* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + count(root->left) + count(root->right);
}

// Function to count the total number of leaf nodes in the BST
int countLeaf(struct Node* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaf(root->left) + countLeaf(root->right);
}

Main Program (bst_count_total_nodes.c)

This file uses the BST library to create a BST, insert nodes, and count the total and leaf nodes.

download code

 
#include <stdio.h>
#include "bst_countNodes.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);

    // Count the total number of nodes
    int totalNodes = count(root);
    printf("Total number of nodes in the BST: %d\n", totalNodes);

    // Count the total number of leaf nodes
    int totalLeafNodes = countLeaf(root);
    printf("Total number of leaf nodes in the BST: %d\n", totalLeafNodes);

    return 0;
}
Table of Contents
BST Operations
BST Counting leaf nodes
Piyu's CS

Computer Science Education

Contact Us

info@piyuscs.com