Re: no :of nodes

Eric Sosman wrote:
> sophia wrote:
>> How good is this function which is used to find  the no: of nodes
>> in each level of the binary tree. ?
>>
>> int arrlev[100];
>>
>> void preorder(struct btree *n,int lev)
>> {
>>        if(!(n))
>>        return;
>>
>>        arrlev[lev]++;
>>        lev++;
>>
>>       preorder(n->left,lev);
>>       preorder(n->right,lev);
>> }
> 
>     1) It will fail badly on a tree with more than a hundred
> levels.  Do such trees really exist?  Try this: write a program
> to build a binary search tree from an input stream of words,
> then feed it a list of ten thousand words -- in alphabetical
> order.
> 
>     2) Even if arrlev[] is made larger, the function is likely
> to fail on very tall trees (or degenerate trees, as above).
....
>     4) You might gain still more speed by using recursion only
> when you encounter a node where both the left and right branches
> are non-NULL.  This also offers some defense against degeneracy.

I'd say that 4) offers excellent defense against (call level overflow) 
degeneracy since the maximum recursion level is less than log2(N)+1.
That doesn't fix the array bounds problem, though.

-- 
Thad