Algorithm

1. If root is NULL, allocate and initialise a new root node.
2. Otherwise compare the new key at each visited node.
3. Move left for a smaller key and right for a larger key.
4. At a NULL child link, attach a checked new node.
5. For an equal key, follow the chosen duplicate policy; this example leaves the tree unchanged.

Example

Insert 50, 30, 70, 20 and 40. The first key becomes root. 30 goes left of 50 and 70 right. 20 goes left of 30; 40 goes right of 30. Inorder traversal is 20, 30, 40, 50, 70.

Memory handling

Set a new node’s child links to NULL. If allocation fails, leave the existing tree valid and report failure. A recursive implementation must return the possibly changed subtree root and the caller must store it, including the first insertion into an empty tree.

Order matters

The same key set can form different shapes for different insertion orders. The values are ordered logically by comparisons, not necessarily by the physical addresses of the nodes. This operation does not perform AVL or red-black balancing.

Complexity

Insertion follows one path of height h, giving O(h) comparisons plus node allocation. Worst case is O(n); a balanced shape gives O(log n). Recursive extra call space is O(h), while an iterative implementation can keep fixed working pointers.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int key; struct Node *left, *right; };
struct Node *insert(struct Node *root, int key, int *ok)
{
    if (root == NULL) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) { *ok = 0; return NULL; }
        node->key = key; node->left = node->right = NULL; return node;
    }
    if (key < root->key) { root->left = insert(root->left, key, ok); }
    else if (key > root->key) { root->right = insert(root->right, key, ok); }
    return root;
}
const struct Node *search(const struct Node *root, int key)
{
    while (root != NULL && root->key != key) { root = key < root->key ? root->left : root->right; }
    return root;
}
struct Node *remove_key(struct Node *root, int key)
{
    if (root == NULL) { return NULL; }
    if (key < root->key) { root->left = remove_key(root->left, key); }
    else if (key > root->key) { root->right = remove_key(root->right, key); }
    else {
        if (root->left == NULL) { struct Node *next = root->right; free(root); return next; }
        if (root->right == NULL) { struct Node *next = root->left; free(root); return next; }
        struct Node *successor = root->right;
        while (successor->left != NULL) { successor = successor->left; }
        root->key = successor->key;
        root->right = remove_key(root->right, successor->key);
    }
    return root;
}
void inorder(const struct Node *root)
{
    if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); }
}
void destroy(struct Node *root)
{
    if (root != NULL) { destroy(root->left); destroy(root->right); free(root); }
}

int main(void)
{
    struct Node *root = NULL; int ok = 1;
    int keys[7] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); puts("Allocation failed"); return 1; }
    }
    printf("Search 40: %s\n", search(root, 40) != NULL ? "Found" : "Not found");
    root = remove_key(root, 20); root = remove_key(root, 30); root = remove_key(root, 50);
    inorder(root); putchar('\n'); destroy(root); root = NULL;
    return 0;
}

Search 40: Found
40 60 70 80