BST insertion algorithm

To insert a key into a BST, search for it from the root. The search ends at a NULL link, and the new node is attached exactly there as a leaf. Duplicates are ignored.

Algorithm (iterative)

Insert(root, x)
1. Create a new node N: N->info = x, N->left = N->right = NULL.
2. If root = NULL: root = N; stop.
3. Set p = root.
4. Repeat:
      if x < p->info:
            if p->left = NULL: p->left = N; stop
            else p = p->left
      else if x > p->info:
            if p->right = NULL: p->right = N; stop
            else p = p->right
      else: x is already present; discard N; stop

Recursive version (C)

struct node *insert(struct node *root, int x) {
    if (root == NULL) {                       /* empty spot found */
        struct node *n = malloc(sizeof(struct node));
        n->info = x; n->left = n->right = NULL;
        return n;
    }
    if (x < root->info)      root->left  = insert(root->left, x);
    else if (x > root->info) root->right = insert(root->right, x);
    return root;                              /* duplicates ignored */
}

Example: inserting 50, 30, 70, 20, 40, 60 gives root 50, left child 30 (children 20, 40) and right child 70 (left child 60). To insert 65: 65 > 50 right; 65 < 70 left; 65 > 60 so it becomes the right child of 60.

Time: O(h), i.e. O(log n) on average and O(n) in the worst case.