Additional Operations on Binary search Tree

 

Algorithms for Additional BST Operations

1. Count Total Number of Nodes

int countNodes(Node* root) {
    if (root == NULL)
        return 0;
    else
        return 1 + countNodes(root->left) + countNodes(root->right);
}

Explanation:
Every node contributes 1 plus the number of nodes in left and right subtrees.

2. Count Number of Leaf Nodes

int countLeafNodes(Node* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    else
        return countLeafNodes(root->left) + countLeafNodes(root->right);
}

Explanation:
A leaf is a node with no left and right children.

3. Count Number of Internal Nodes

int countInternalNodes(Node* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 0;
    else
        return 1 + countInternalNodes(root->left) + countInternalNodes(root->right);
}

Explanation:
Internal nodes are all nodes except leaves.

4. Height of the Tree

int height(Node* root) {
    if (root == NULL)
        return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (leftHeight > rightHeight)
        return leftHeight + 1;
    else
        return rightHeight + 1;
}

Explanation:
Height = 1 + max(height of left, height of right).

5. Search for a Key in BST

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

Explanation:
Uses the BST property to decide whether to go left or right.

6. Find Minimum in BST

Node* findMin(Node* root) {
    if (root == NULL)
        return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

Explanation:
The leftmost node is the minimum.

7. Find Maximum in BST

Node* findMax(Node* root) {
    if (root == NULL)
        return NULL;
    while (root->right != NULL)
        root = root->right;
    return root;
}

Explanation:
The rightmost node is the maximum.

✅ All these operations are recursive except min/max (iterative).
✅ Time complexity: O(n) for counts and height, O(h) for search/min/max (where h = height of tree).


Menu Driven C Program 

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

// Structure for a BST node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 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 = newNode->right = NULL;
    return newNode;
}

// Insert into 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;
}

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

// Pre-order Traversal
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Post-order Traversal
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

// Count total nodes
int countNodes(struct Node* root) {
    if (root == NULL)
        return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Count leaf nodes
int countLeafNodes(struct Node* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

// Count internal nodes
int countInternalNodes(struct Node* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 0;
    return 1 + countInternalNodes(root->left) + countInternalNodes(root->right);
}

// Height of tree
int height(struct Node* root) {
    if (root == NULL)
        return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Search for a key
struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}

// Find Minimum
struct Node* findMin(struct Node* root) {
    if (root == NULL)
        return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

// Find Maximum
struct Node* findMax(struct Node* root) {
    if (root == NULL)
        return NULL;
    while (root->right != NULL)
        root = root->right;
    return root;
}

int main() {
    struct Node* root = NULL;
    int choice, value, key;
    struct Node* temp;

    while (1) {
        printf("\n--- Binary Search Tree Menu ---\n");
        printf("1. Insert\n");
        printf("2. In-order Traversal\n");
        printf("3. Pre-order Traversal\n");
        printf("4. Post-order Traversal\n");
        printf("5. Count Total Nodes\n");
        printf("6. Count Leaf Nodes\n");
        printf("7. Count Internal Nodes\n");
        printf("8. Height of Tree\n");
        printf("9. Search\n");
        printf("10. Find Minimum\n");
        printf("11. Find Maximum\n");
        printf("12. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
        case 1:
            printf("Enter value to insert: ");
            scanf("%d", &value);
            root = insert(root, value);
            break;
        case 2:
            printf("In-order Traversal: ");
            inorder(root);
            printf("\n");
            break;
        case 3:
            printf("Pre-order Traversal: ");
            preorder(root);
            printf("\n");
            break;
        case 4:
            printf("Post-order Traversal: ");
            postorder(root);
            printf("\n");
            break;
        case 5:
            printf("Total Nodes = %d\n", countNodes(root));
            break;
        case 6:
            printf("Leaf Nodes = %d\n", countLeafNodes(root));
            break;
        case 7:
            printf("Internal Nodes = %d\n", countInternalNodes(root));
            break;
        case 8:
            printf("Height of Tree = %d\n", height(root));
            break;
        case 9:
            printf("Enter key to search: ");
            scanf("%d", &key);
            temp = search(root, key);
            if (temp != NULL)
                printf("Key %d found in BST.\n", key);
            else
                printf("Key %d not found.\n", key);
            break;
        case 10:
            temp = findMin(root);
            if (temp != NULL)
                printf("Minimum Value = %d\n", temp->data);
            else
                printf("Tree is empty.\n");
            break;
        case 11:
            temp = findMax(root);
            if (temp != NULL)
                printf("Maximum Value = %d\n", temp->data);
            else
                printf("Tree is empty.\n");
            break;
        case 12:
            exit(0);
        default:
            printf("Invalid choice. Try again.\n");
        }
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and Evaluation Scheme  Model Question Paper and Answers PCCST303 Data Structures and Algorithms Try the following programs in lab to understand the theory better 1.Basic Concepts of Data Structures Stacks and Queues     Data Structures and Data Abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis          Array as a Data Structure     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to ...
Read more

Memory Allocation - First Fit

  Memory Allocation Strategy When a program requests memory from the operating system (OS) — say for creating variables, arrays, or objects — the OS must decide where in the memory to place this data. This decision-making is known as a Memory Allocation Strategy . In dynamic memory allocation, main memory (RAM) is managed in chunks called blocks . As programs request and release memory, the memory space gets fragmented into free and occupied blocks. So, an important task for the OS is to find an appropriate free block when a program requests memory. To manage this efficiently, different allocation strategies are used. First Fit Memory Allocation Strategy Definition : In the First Fit strategy, the OS searches from the beginning of memory and allocates the first free block that is large enough to satisfy the request. It doesn't check all blocks. As soon as a large enough block is found, allocation happens. Example : Assume free memory blocks of sizes: 200KB , 500KB ,...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more