Implement BST using doubly linked list

A BST node is implemented as a doubly-linked structure: each node holds the data and two pointers, left (previous) and right (next), pointing to its two children. Together with the root pointer, this represents the whole tree.

Algorithm

Node: info, left, right (both NULL for a new node)

Insert(root, x):
  1. create node N with info = x, left = right = NULL
  2. if root = NULL        root = N, stop
  3. p = root
  4. loop:
        if x < p->info:
              if p->left = NULL  then p->left = N, stop
              else p = p->left
        else if x > p->info:
              if p->right = NULL then p->right = N, stop
              else p = p->right
        else  stop (duplicate, discard N)

Search(root, x): follow left if x < info, right if x > info,
                 until found or NULL.
Inorder(p): if p != NULL: Inorder(p->left); visit p; Inorder(p->right)

C implementation

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

struct node {
    int info;
    struct node *left, *right;     /* two links: doubly linked node */
};

struct node *newnode(int x) {
    struct node *n = (struct node *)malloc(sizeof(struct node));
    n->info = x; n->left = n->right = NULL;
    return n;
}

struct node *insert(struct node *root, int x) {
    struct node *n = newnode(x), *p, *q = NULL;
    if (root == NULL) return n;            /* first node becomes root */
    p = root;
    while (p != NULL) {                    /* q trails p as its parent */
        q = p;
        if (x < p->info)       p = p->left;
        else if (x > p->info)  p = p->right;
        else { free(n); return root; }     /* duplicate */
    }
    if (x < q->info) q->left = n; else q->right = n;
    return root;
}

struct node *search(struct node *p, int x) {
    while (p != NULL && p->info != x)
        p = (x < p->info) ? p->left : p->right;
    return p;
}

void inorder(struct node *p) {
    if (p != NULL) { inorder(p->left); printf("%d ", p->info); inorder(p->right); }
}

int main(void) {
    struct node *root = NULL;
    int a[] = {50, 30, 70, 20, 40}, i;
    for (i = 0; i < 5; i++) root = insert(root, a[i]);
    inorder(root);                         /* 20 30 40 50 70 */
    printf("\n%s\n", search(root, 40) ? "found" : "not found");
    return 0;
}

Output: 20 30 40 50 70 then found. Insert and search cost O(h).