Insert Node in Binary Search Tree

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

// Define a structure for a node in the BST
struct Node {
    int data;              // Data part of the node
    struct Node* left;     // Pointer to the left child
    struct Node* right;    // Pointer to the right child
};

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;  // Set the data
    newNode->left = NULL;   // Initialize left child as NULL
    newNode->right = NULL;  // Initialize right child as NULL
    return newNode;
}

// Function to insert a node in the BST
struct Node* insert(struct Node* root, int value) {
    // If the tree is empty, return a new node
    if (root == NULL) {
        return createNode(value);
    }
    
    // Otherwise, recur down the tree
    if (value < root->data) {
        // If the value to be inserted is smaller than the root, insert in the left subtree
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        // If the value to be inserted is greater than the root, insert in the right subtree
        root->right = insert(root->right, value);
    }

    // Return the unchanged root pointer
    return root;
}

// Function to perform an in-order traversal of the BST
void inOrder(struct Node* root) {
    if (root != NULL) {
        inOrder(root->left);          // Visit left subtree
        printf("%d ", root->data);    // Print the node's data
        inOrder(root->right);         // Visit right subtree
    }
}

int main() {
    struct Node* root = NULL;  // Start with an empty tree
    int values[] = {50, 30, 20, 40, 70, 60, 80};  // Values to insert into the BST
    int n = sizeof(values) / sizeof(values[0]);

    // Insert values into the BST
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }

    // Print the in-order traversal of the BST
    printf("In-order traversal of the BST: ");
    inOrder(root);
    printf("\n");

    return 0;
}

Explanation:

1. Node Structure Definition:
   • We define a Node structure using struct in C.
   • Each node has three parts:
     • data: An integer to store the value.
     • left: A pointer to the left child.
     • right: A pointer to the right child.
2. Creating a New Node:
   • createNode(int value) is a function that allocates memory for a new node and initializes it with the given value.
   • It sets left and right pointers to NULL because, initially, the new node does not have any children.
3. Inserting a Node into the BST:
   • The insert(struct Node* root, int value) function inserts a new node with the given value into the BST.
   • If the root is NULL, it means the tree is empty or we have reached a leaf position, so a new node is created and returned.
   • If the value is less than the root‘s data, we recursively insert it into the left subtree.
   • If the value is greater than the root‘s data, we recursively insert it into the right subtree.
   • After insertion, we return the unchanged root pointer to maintain the tree’s structure.
4. In-order Traversal:
   • The inOrder(struct Node* root) function traverses the BST in in-order fashion (left subtree -> root -> right subtree).
   • It prints out the nodes in sorted order because of the properties of BST.
5. Main Function:
   • Starts with an empty BST (root = NULL).
   • An array values contains the integers to be inserted.
   • We iterate through each value and insert it into the BST using the insert function.
   • Finally, we print the in-order traversal of the BST to verify the nodes are inserted correctly.

Output:

When you run the above program, the output will display the in-order traversal of the BST:

In-order traversal of the BST: 20 30 40 50 60 70 80

Explanation of Output:

• The in-order traversal prints the nodes in ascending order because, in a BST, for each node:
  • Values in the left subtree are smaller.
  • Values in the right subtree are larger.
• 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.