Algorithm Alley

The Cost of Recursion

By Jon Bentley

Dr. Dobb's Journal June 1998

<B>(a)</B>
typedef struct tnode *Tptr;
typedef struct tnode {
    int val;
    Tptr lo, hi;
} Tnode;
<B>(b)</B>
int rbstsearch(Tptr p, int t)
{  if (!p)
       return -1;
   if (t == p->val)
       return 1;
   if (t < p->val)
       return rbstsearch(p->lo, t);
   return rbstsearch(p->hi, t);
}
<B>(c)</B>
int ibstsearch(int t)
{  Tptr p;
   for (p=root; p; ) {
       if (t == p->val)
           return 1;
       p=(t<p->val) ? p->lo : p->hi;
   }
   return -1;
}
<B>(d)</B>
Tptr rinsert(Tptr p, int t)
{   if (p) {
        if (t < p->val)
            p->lo = rinsert(p->lo, t);
        else
            p->hi = rinsert(p->hi, t);
    } else {
        p = (Tptr) malloc(sizeof(Tnode));
        p->lo = p->hi = 0;
        p->val = t;
    }
    return p;
}

Example 3: (a) Each node in a binary search tree contains an integer value and two pointers to subtrees; (b) recursive search function returns 1 if the value t is in the tree, -1 if the value is not present; (c) iterative version; (d) when p is null, it makes a new node.