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 (b) 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.   

            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;
}
 Assignment 1: Set B (a):
 
Write a C program which uses Binary Search tree Library and Implememnts following function with recursion :
tree_copy(t) – create another BST whch is exact copy of BST which is passed as parameter. 
int compare(t1,t2) – compares two binary search trees and retures 1 if they are equal and o otherwise. 
download code

 

BST Library: bst.h

#ifndef BST_H

#define BST_H

#include <stdio.h>

#include <stdlib.h>

// Structure for a BST node

typedef struct Node {

    int data;

    struct Node *left, *right;

} Node;

// Function prototypes

Node* createNode(int data);

Node* insert(Node* root, int data);

void inorder(Node* root);

Node* tree_copy(Node* root);

int compare(Node* t1, Node* t2);

void freeTree(Node* root);

#endif

BST Library Implementation: bst.c

#include “bst.h”

// Function to create a new node

Node* createNode(int data) {

    Node* newNode = (Node*)malloc(sizeof(Node));

    if (!newNode) {

        printf(“Memory error\n”);

        return NULL;

    }

    newNode->data = data;

    newNode->left = newNode->right = NULL;

    return newNode;

}

// Function to insert a node in BST

Node* insert(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 perform in-order traversal (for display)

void inorder(Node* root) {

    if (root == NULL)

        return;

    inorder(root->left);

    printf(“%d “, root->data);

    inorder(root->right);

}

// Function to create a copy of a BST

Node* tree_copy(Node* root) {

    if (root == NULL)

        return NULL;

    Node* newRoot = createNode(root->data);

    newRoot->left = tree_copy(root->left);

    newRoot->right = tree_copy(root->right);

    return newRoot;

}

// Function to compare two BSTs

int compare(Node* t1, Node* t2) {

    if (t1 == NULL && t2 == NULL)

        return 1;

    if (t1 == NULL || t2 == NULL)

        return 0;

    if (t1->data != t2->data)

        return 0;

    return compare(t1->left, t2->left) && compare(t1->right, t2->right);

}

// Function to free the BST

void freeTree(Node* root) {

    if (root == NULL)

        return;

    freeTree(root->left);

    freeTree(root->right);

    free(root);

}

Main Program Using BST Library: copy_compare.c

#include “bst.h”

int main() {

    Node* root1 = NULL;

    root1 = insert(root1, 50);

    root1 = insert(root1, 30);

    root1 = insert(root1, 70);

    root1 = insert(root1, 20);

    root1 = insert(root1, 40);

    root1 = insert(root1, 60);

    root1 = insert(root1, 80);

    printf(“Original BST (In-order): “);

    inorder(root1);

    printf(“\n”);

    // Copy the tree

    Node* root2 = tree_copy(root1);

    printf(“Copied BST (In-order): “);

    inorder(root2);

    printf(“\n”);

    // Compare trees

    if (compare(root1, root2))

        printf(“Both trees are identical.\n”);

    else

        printf(“Trees are not identical.\n”);

    // Free memory

    freeTree(root1);

    freeTree(root2);

    return 0;

}

 Assignment 1: Set C (a):
 
Write a C program which uses binary search tree library and implememnts following two functions : 

int sumodd(t) – returns sum of all odd numbers from BST,

intsumeven(t) – returns sum of all even numbers from BSt.

mirror(t) – converts given tree into its mirror image.

download code

1. bstlib.h (BST Library Header)

#ifndef BSTLIB_H
#define BSTLIB_H

#include <stdio.h>  // For printf in implementations
#include <stdlib.h> // For malloc

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

// BST operations
Node* createNode(int value);
Node* insert(Node* root, int value);
void inorder(Node* root);
void freeTree(Node* root);

// Assignment functions
int sumodd(Node* t);
int sumeven(Node* t);
void mirror(Node* t);

#endif

2. bstlib.c (BST Library Implementation)

 
#include "bstlib.h"

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Node* insert(Node* root, int value) {
    if (root == NULL) return createNode(value);
    
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // Ignore duplicates
    return root;
}

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int sumodd(Node* t) {
    if (t == NULL) return 0;
    return (t->data % 2 != 0 ? t->data : 0) + sumodd(t->left) + sumodd(t->right);
}

int sumeven(Node* t) {
    if (t == NULL) return 0;
    return (t->data % 2 == 0 ? t->data : 0) + sumeven(t->left) + sumeven(t->right);
}

void mirror(Node* t) {
    if (t == NULL) return;
    
    Node* temp = t->left;
    t->left = t->right;
    t->right = temp;
    
    mirror(t->left);
    mirror(t->right);
}

3. main.c (Program Using BST Library)

 
#include "bstlib.h"

int main() {
    Node* root = NULL;
    int values[] = {50, 30, 20, 40, 70, 60, 80, 15, 25, 35, 45};
    int n = sizeof(values)/sizeof(values[0]);
    
    // Build BST
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }
    
    printf("Original BST (inorder): ");
    inorder(root);
    printf("\n");
    
    printf("Sum of odd numbers: %d\n", sumodd(root));
    printf("Sum of even numbers: %d\n", sumeven(root));
    
    mirror(root);
    printf("Mirror BST (inorder): ");
    inorder(root);
    printf("\n");
    
    freeTree(root);
    return 0;
}

 

Table of Contents
BST Operations
BST Counting leaf nodes
Piyu's CS

Computer Science Education

Contact Us

info@piyuscs.com