5. b). Write a C function to insert elements in a BST

Question

Write a C function to insert elements in a BST.

Solution

Inserting Elements in a Binary Search Tree (BST)

A Binary Search Tree (BST) is a data structure that maintains sorted order of elements. Each node in a BST has a maximum of two children, where the left child contains values less than the parent node, and the right child contains values greater than the parent node. Inserting an element into a BST involves finding the correct position for the new value while maintaining this order.

Steps to Insert an Element in a BST

1. Define the Node Structure: Create a structure for the tree node that includes the value and pointers to left and right children.
2. Check for Null: If the current node is null, create a new node with the given value and return it.
3. Compare Values: If the value to be inserted is less than the current node’s value, recursively call the insert function on the left child. If it is greater, call it on the right child.
4. Return the Node: After inserting the new node, return the unchanged node pointer to maintain the tree structure.

Sample C Function

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* insert(struct Node* node, int value) {
    if (node == NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (value < node->data) {
        node->left = insert(node->left, value);
    } else {
        node->right = insert(node->right, value);
    }
    return node;
}

Tip

Always ensure to check for memory allocation success when creating new nodes to avoid memory leaks or crashes.