Binary Tree Operations

Basic operations:

OperationDescription
1. Create a node        Make a new node
2. Insert a node            Insert into the binary  tree
3. Traversals        Inorder, Preorder, Postorder
4. Search for a node        Find a node
5. Find height of tree        Max depth
6. Count nodes        Total nodes, leaf nodes
7. Delete a tree        Free all nodes

🌳 Binary Tree Algorithms

1. Create a New Node

Algorithm:

  1. Allocate memory for a new node.

  2. Set the node’s data field to the given value.

  3. Set the node’s left and right pointers to NULL.

  4. Return the newly created node.

2. Insert a Node

👉 (For a simple binary tree, level order insertion)

Algorithm:

  1. If the tree is empty, create a new node and set it as root.

  2. Otherwise:

    • Use a queue to perform level order traversal.

    • For each node:

      • If the left child is NULL, insert the new node as the left child and stop.

      • Else, add the left child to the queue.

      • If the right child is NULL, insert the new node as the right child and stop.

      • Else, add the right child to the queue.

3. Traversal Algorithms

(a) Inorder Traversal (Left → Root → Right)

Algorithm:

  1. If the current node is not NULL:

    • Traverse the left subtree.

    • Visit (print) the current node.

    • Traverse the right subtree.

(b) Preorder Traversal (Root → Left → Right)

Algorithm:

  1. If the current node is not NULL:

    • Visit (print) the current node.

    • Traverse the left subtree.

    • Traverse the right subtree.

(c) Postorder Traversal (Left → Right → Root)

Algorithm:

  1. If the current node is not NULL:

    • Traverse the left subtree.

    • Traverse the right subtree.

    • Visit (print) the current node.

4. Search for a Node

Algorithm:

  1. If the tree is empty, return FALSE.

  2. If the current node’s data matches the key, return TRUE.

  3. Recursively search the left and right subtrees.

  4. If the key is found in any subtree, return TRUE.

  5. Otherwise, return FALSE.

5. Find the Height of the Tree

Algorithm:

  1. If the tree is empty, return -1 (or 0 depending on definition).

  2. Recursively find the height of the left and right subtrees.

  3. Return 1 + maximum of left and right subtree heights.

6. Count Total Number of Nodes

Algorithm:

  1. If the tree is empty, return 0.

  2. Recursively count the number of nodes in the left and right subtrees.

  3. Total nodes = 1 (current node) + left count + right count.

7. Count Number of Leaf Nodes

Algorithm:

  1. If the tree is empty, return 0.

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

  3. Otherwise:

    • Recursively count the leaf nodes in the left and right subtrees.

    • Sum them and return.

8. Delete the Entire Tree

Algorithm:

  1. If the current node is NULL, return.

  2. Recursively delete the left subtree.

  3. Recursively delete the right subtree.

  4. Free the memory for the current node.


✅ Menu-Driven C Program for Binary Tree Operations

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

// Structure for a Binary Tree Node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new Node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory error!\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Insert a Node (level order insertion)
struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }

    // Using a simple queue for level order insertion
    struct Node* queue[100];
    int front = 0, rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        struct Node* temp = queue[front++];

        if (temp->left == NULL) {
            temp->left = createNode(value);
            return root;
        } else {
            queue[rear++] = temp->left;
        }

        if (temp->right == NULL) {
            temp->right = createNode(value);
            return root;
        } else {
            queue[rear++] = temp->right;
        }
    }
    return root;
}

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

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

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

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

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

// 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);
}

// Delete Entire Tree
void deleteTree(struct Node* root) {
    if (root == NULL) {
        return;
    }
    deleteTree(root->left);
    deleteTree(root->right);
    printf("Deleting node: %d\n", root->data);
    free(root);
}

// Main Menu
int main() {
    struct Node* root = NULL;
    int choice, value, key, found;

    while (1) {
        printf("\n\n--- Binary Tree Menu ---\n");
        printf("1. Insert Node\n");
        printf("2. Inorder Traversal\n");
        printf("3. Preorder Traversal\n");
        printf("4. Postorder Traversal\n");
        printf("5. Search a Node\n");
        printf("6. Find Height of Tree\n");
        printf("7. Count Total Nodes\n");
        printf("8. Count Leaf Nodes\n");
        printf("9. Delete Entire Tree\n");
        printf("10. 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);
                printf("Node inserted.\n");
                break;

            case 2:
                printf("Inorder Traversal: ");
                inorder(root);
                printf("\n");
                break;

            case 3:
                printf("Preorder Traversal: ");
                preorder(root);
                printf("\n");
                break;

            case 4:
                printf("Postorder Traversal: ");
                postorder(root);
                printf("\n");
                break;

            case 5:
                printf("Enter value to search: ");
                scanf("%d", &key);
                found = search(root, key);
                if (found)
                    printf("Node found.\n");
                else
                    printf("Node not found.\n");
                break;

            case 6:
                printf("Height of tree: %d\n", height(root));
                break;

            case 7:
                printf("Total nodes in tree: %d\n", countNodes(root));
                break;

            case 8:
                printf("Total leaf nodes in tree: %d\n", countLeafNodes(root));
                break;

            case 9:
                deleteTree(root);
                root = NULL;
                printf("Tree deleted.\n");
                break;

            case 10:
                printf("Exiting...\n");
                deleteTree(root); // clean up before exiting
                exit(0);

            default:
                printf("Invalid choice! Please 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  1.Basic Concepts of Data Structures     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     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 prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
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

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more