All dynamic-set search operations can be supported in O(h) time, where h is the height of the tree.

• h = O(lg n) for a balanced binary tree (and for an average tree built by adding nodes in random order.
• h = O(n) for an unbalanced tree that resembles a linear chain of n nodes in the worst case.

typedef struct tree {
    item_type item;      /* data item */
    struct tree *parent; /* pointer to parent */
    struct tree *left;   /* pointer to left child */
    struct tree *right;  /* pointer to right child */
} tree;

tree *search_tree(tree *l, item_type x) {
    if (l == NULL) return(NULL);
    if (l->item == x) return(l);
    if (x < l->item)
        return(search_tree(l->left, x));
    else
        return(search_tree(l->right, x));
}

tree *find_minimum(tree *t) {
    tree *min; /* pointer to minimum */
    if (t == NULL) return(NULL);
    min = t;
    while (min->left != NULL)
        min = min->left;
    return(min);
}

void traverse_tree(tree *l) {
    if (l != NULL) {
        traverse_tree(l->left);
        process_item(l->item);
        traverse_tree(l->right);
    }
}

Each item is processed once during the course of traversal, which runs in O(n) time, where n denotes the number of nodes in the tree.

insert_tree(tree **l, item_type x, tree *parent) {
    tree *p; /* temporary pointer */
    if (*l == NULL) {
        p = malloc(sizeof(tree)); /* allocate new node */
        p->item = x;
        p->left = p->right = NULL;
        p->parent = parent;
        *l = p; /* link into parent’s record */
        return;
    }
    if (x < (*l)->item)
        insert_tree(&((*l)->left), x, *l);
    else
        insert_tree(&((*l)->right), x, *l);
}