Re: no :of nodes

Keith Thompson wrote:
> Thad Smith <ThadSmith@[EMAIL PROTECTED]
> writes:
>> 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. ?
> 
> [snip]
> 
>>>     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.
> 
> Does it?  It limits recursion if the tree is a linear vine, and can
> reduce it substantially in some other cases, but what if each node on
> the leftmost vine has a single node as its right child?  Then the
> depth of recursion could be on the order of 1/2 the number of nodes.
> [...]

     That's why I only claimed "some" defense against degeneracy.
Even in the tree you describe one might get lucky: if when
faced with a two-way branch the function always recursed to the
right and looped to the left, there'd be no trouble.  Of course,
then a tree that leaned the other direction would be bad.  So
would a zig-zag arrangement where the "trunk" went left and right
alternately while the "twigs" branched right and left.

-- 
Eric Sosman
esosman@[EMAIL PROTECTED]