The Cost of Recursion

By Jon Bentley

Dr. Dobb's Journal June 1998

void iinsert(int t)
{   Tptr p, q;
    Tptr next = (Tptr) malloc(sizeof(Tnode));
    if (!root)
        root = next;
    else {
        for (q = root; q; ) {
            p = q;
            q = (t < p->val) ? q->lo : q->hi;
        }
        if (t < p->val)
            p->lo = next;
        else
            p->hi = next;
    }
    next->lo = next->hi = 0;
    next->val = t;
}

Example 4: Iterative function to insert a new node into a binary search tree.

Back to Article