{"id":656,"date":"2024-10-10T13:41:46","date_gmt":"2024-10-10T08:11:46","guid":{"rendered":"https:\/\/codexplained.in\/?p=656"},"modified":"2025-11-24T15:57:23","modified_gmt":"2025-11-24T10:27:23","slug":"insert-node-in-binary-search-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=656","title":{"rendered":"Insert Node in Binary Search Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define a structure for a node in the BST\nstruct Node {\n    int data;              \/\/ Data part of the node\n    struct Node* left;     \/\/ Pointer to the left child\n    struct Node* right;    \/\/ Pointer to the right child\n};\n\n\/\/ Function to create a new node\nstruct Node* createNode(int value) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = value;  \/\/ Set the data\n    newNode->left = NULL;   \/\/ Initialize left child as NULL\n    newNode->right = NULL;  \/\/ Initialize right child as NULL\n    return newNode;\n}\n\n\/\/ Function to insert a node in the BST\nstruct Node* insert(struct Node* root, int value) {\n    \/\/ If the tree is empty, return a new node\n    if (root == NULL) {\n        return createNode(value);\n    }\n    \n    \/\/ Otherwise, recur down the tree\n    if (value < root->data) {\n        \/\/ If the value to be inserted is smaller than the root, insert in the left subtree\n        root->left = insert(root->left, value);\n    } else if (value > root->data) {\n        \/\/ If the value to be inserted is greater than the root, insert in the right subtree\n        root->right = insert(root->right, value);\n    }\n\n    \/\/ Return the unchanged root pointer\n    return root;\n}\n\n\/\/ Function to perform an in-order traversal of the BST\nvoid inOrder(struct Node* root) {\n    if (root != NULL) {\n        inOrder(root->left);          \/\/ Visit left subtree\n        printf("%d ", root->data);    \/\/ Print the node's data\n        inOrder(root->right);         \/\/ Visit right subtree\n    }\n}\n\nint main() {\n    struct Node* root = NULL;  \/\/ Start with an empty tree\n    int values[] = {50, 30, 20, 40, 70, 60, 80};  \/\/ Values to insert into the BST\n    int n = sizeof(values) \/ sizeof(values[0]);\n\n    \/\/ Insert values into the BST\n    for (int i = 0; i < n; i++) {\n        root = insert(root, values[i]);\n    }\n\n    \/\/ Print the in-order traversal of the BST\n    printf("In-order traversal of the BST: ");\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. Node Structure Definition<\/strong>:\n
      \n
    • We define a Node<\/code> structure using struct<\/code> in C.<\/li>\n\n\n\n
    • Each node has three parts:\n
        \n
      • data<\/code>: An integer to store the value.<\/li>\n\n\n\n
      • left<\/code>: A pointer to the left child.<\/li>\n\n\n\n
      • right<\/code>: A pointer to the right child.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Creating a New Node<\/strong>:\n
          \n
        • createNode(int value)<\/code> is a function that allocates memory for a new node and initializes it with the given value.<\/li>\n\n\n\n
        • It sets left<\/code> and right<\/code> pointers to NULL<\/code> because, initially, the new node does not have any children.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Inserting a Node into the BST<\/strong>:\n
            \n
          • The insert(struct Node* root, int value)<\/code> function inserts a new node with the given value into the BST.<\/li>\n\n\n\n
          • If the root<\/code> is NULL<\/code>, it means the tree is empty or we have reached a leaf position, so a new node is created and returned.<\/li>\n\n\n\n
          • If the value<\/code> is less than the root<\/code>‘s data<\/code>, we recursively insert it into the left subtree.<\/li>\n\n\n\n
          • If the value<\/code> is greater than the root<\/code>‘s data<\/code>, we recursively insert it into the right subtree.<\/li>\n\n\n\n
          • After insertion, we return the unchanged root<\/code> pointer to maintain the tree’s structure.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • In-order Traversal<\/strong>:\n
              \n
            • The inOrder(struct Node* root)<\/code> function traverses the BST in in-order fashion (left subtree -> root -> right subtree).<\/li>\n\n\n\n
            • It prints out the nodes in sorted order because of the properties of BST.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Main Function<\/strong>:\n
                \n
              • Starts with an empty BST (root = NULL<\/code>).<\/li>\n\n\n\n
              • An array values<\/code> contains the integers to be inserted.<\/li>\n\n\n\n
              • We iterate through each value and insert it into the BST using the insert<\/code> function.<\/li>\n\n\n\n
              • Finally, we print the in-order traversal of the BST to verify the nodes are inserted correctly.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Output:<\/h3>\n\n\n\n
                When you run the above program, the output will display the in-order traversal of the BST:<\/p>\n\n\n\n
                In-order traversal of the BST: 20 30 40 50 60 70 80\n<\/code><\/pre>\n\n\n\n
                Explanation of Output:<\/h3>\n\n\n\n
                  \n
                • The in-order traversal prints the nodes in ascending order because, in a BST, for each node:\n
                    \n
                  • Values in the left subtree are smaller.<\/li>\n\n\n\n
                  • Values in the right subtree are larger.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • For the given set of values (50, 30, 20, 40, 70, 60, 80), the nodes are arranged in such a way that when we traverse it in in-order, we get 20 30 40 50 60 70 80<\/code>.<\/li>\n<\/ul>\n