{"id":548,"date":"2024-10-19T13:53:50","date_gmt":"2024-10-19T08:23:50","guid":{"rendered":"https:\/\/codexplained.in\/?p=548"},"modified":"2025-11-24T15:32:14","modified_gmt":"2025-11-24T10:02:14","slug":"implement-binary-search-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=548","title":{"rendered":"Implement Binary Search Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define the structure for a node in the BST\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Function to create a new node\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->left = NULL;\n    newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function to insert a new node in the BST\nstruct Node* insert(struct Node* root, int data) {\n    if (root == NULL) {\n        return createNode(data);\n    }\n\n    if (data < root->data) {\n        root->left = insert(root->left, data);\n    } else if (data > root->data) {\n        root->right = insert(root->right, data);\n    }\n\n    return root;\n}\n\n\/\/ Function to perform in-order traversal (left, root, right)\nvoid inOrder(struct Node* root) {\n    if (root != NULL) {\n        inOrder(root->left);\n        printf("%d ", root->data);\n        inOrder(root->right);\n    }\n}\n\n\/\/ Function to search for a value in the BST\nstruct Node* search(struct Node* root, int key) {\n    if (root == NULL || root->data == key) {\n        return root;\n    }\n\n    if (key < root->data) {\n        return search(root->left, key);\n    }\n\n    return search(root->right, key);\n}\n\n\/\/ Function to find the minimum value node in a BST\nstruct Node* findMin(struct Node* node) {\n    struct Node* current = node;\n\n    while (current && current->left != NULL) {\n        current = current->left;\n    }\n\n    return current;\n}\n\n\/\/ Function to delete a node from the BST\nstruct Node* deleteNode(struct Node* root, int key) {\n    if (root == NULL) {\n        return root;\n    }\n\n    \/\/ Recur down the tree\n    if (key < root->data) {\n        root->left = deleteNode(root->left, key);\n    } else if (key > root->data) {\n        root->right = deleteNode(root->right, key);\n    } else {\n        \/\/ Node to be deleted found\n\n        \/\/ Node with only one child or no child\n        if (root->left == NULL) {\n            struct Node* temp = root->right;\n            free(root);\n            return temp;\n        } else if (root->right == NULL) {\n            struct Node* temp = root->left;\n            free(root);\n            return temp;\n        }\n\n        \/\/ Node with two children: Get the inorder successor\n        struct Node* temp = findMin(root->right);\n\n        \/\/ Copy the inorder successor's data to this node\n        root->data = temp->data;\n\n        \/\/ Delete the inorder successor\n        root->right = deleteNode(root->right, temp->data);\n    }\n\n    return root;\n}\n\n\/\/ Main function to test the BST\nint main() {\n    struct Node* root = NULL;\n\n    \/\/ Insert nodes into the BST\n    root = insert(root, 50);\n    root = insert(root, 30);\n    root = insert(root, 20);\n    root = insert(root, 40);\n    root = insert(root, 70);\n    root = insert(root, 60);\n    root = insert(root, 80);\n\n    printf("In-order traversal of the BST: ");\n    inOrder(root);\n    printf("\\n");\n\n    \/\/ Search for a value\n    int key = 40;\n    struct Node* foundNode = search(root, key);\n    if (foundNode != NULL) {\n        printf("Node %d found in the BST.\\n", key);\n    } else {\n        printf("Node %d not found in the BST.\\n", key);\n    }\n\n    \/\/ Delete a node\n    root = deleteNode(root, 20);\n    printf("In-order traversal after deleting 20: ");\n    inOrder(root);\n    printf("\\n");\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation:<\/h3>\n\n\n\n
    \n
  1. Structure Definition<\/strong>:\n
      \n
    • struct Node<\/code>: Represents a node of the BST. It contains:\n
        \n
      • data<\/code>: The value of the node.<\/li>\n\n\n\n
      • left<\/code>: Pointer to the left child.<\/li>\n\n\n\n
      • right<\/code>: Pointer to the right child.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Creating a Node<\/strong>:\n
          \n
        • createNode(int data)<\/code>: Allocates memory for a new node, sets its data, and initializes left and right pointers to NULL<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Inserting a Node<\/strong>:\n
            \n
          • insert(struct Node* root, int data)<\/code>: Recursively inserts a new node:\n
              \n
            • If root<\/code> is NULL<\/code>, the new node is inserted at this position.<\/li>\n\n\n\n
            • If data<\/code> is less than the current node’s data, it is inserted in the left subtree.<\/li>\n\n\n\n
            • If data<\/code> is greater, it is inserted in the right subtree.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • In-order Traversal<\/strong>:\n
                \n
              • inOrder(struct Node* root)<\/code>: Prints nodes in ascending order by recursively visiting the left subtree, root, and then the right subtree.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • Searching<\/strong>:\n
                  \n
                • search(struct Node* root, int key)<\/code>: Recursively searches for key<\/code>:\n
                    \n
                  • If key<\/code> matches the current node\u2019s data, it is found.<\/li>\n\n\n\n
                  • If key<\/code> is less, search the left subtree.<\/li>\n\n\n\n
                  • If key<\/code> is greater, search the right subtree.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • Deleting a Node<\/strong>:\n
                      \n
                    • deleteNode(struct Node* root, int key)<\/code>: Removes a node while maintaining BST properties:\n
                        \n
                      • Searches for the key<\/code> to delete.<\/li>\n\n\n\n
                      • Handles three cases:\n
                          \n
                        • Node with only one child or no child.<\/li>\n\n\n\n
                        • Node with two children: Replaces the node with its in-order successor (minimum node from the right subtree).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                        • Main Function<\/strong>:\n
                            \n
                          • Tests the BST by inserting nodes, performing an in-order traversal, searching for a value, deleting a node, and displaying the modified tree.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                            In-order traversal of the BST: 20 30 40 50 60 70 80 \nNode 40 found in the BST.\nIn-order traversal after deleting 20: 30 40 50 60 70 80 <\/code><\/pre>\n\n\n\n
                            Explanation of Output:<\/h3>\n\n\n\n
                              \n
                            • In-order Traversal<\/strong>: Displays the BST elements in sorted order.<\/li>\n\n\n\n
                            • Node 40 found<\/strong>: Indicates that the search operation successfully located the node with value 40<\/code>.<\/li>\n\n\n\n
                            • After Deletion<\/strong>: Shows the in-order traversal after deleting the node with value 20<\/code>.<\/li>\n<\/ul>\n