Velocity Reviews > no :of nodes

# no :of nodes

sophia
Guest
Posts: n/a

 05-07-2008
Dear all,

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);
}

Walter Roberson
Guest
Posts: n/a

 05-07-2008
In article <(E-Mail Removed)>,
sophia <(E-Mail Removed)> 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]++;

When you restrict the number of levels in the counters (which
you do in your declaration of arrlev), then before you write
into arrlev[lev] you need to check that you are not overflowing
the end of the array.

> lev++;
>
> preorder(n->left,lev);
> preorder(n->right,lev);

You could avoid a bunch of do-nothing calls:

if (n->left) preorder(n->left,lev);
if (n->right) preorder(n->right,lev);

>}

--
"I want to be remembered as the guy who gave his all whenever
he was on the field." -- Walter Payton

fred.l.kleinschmidt@boeing.com
Guest
Posts: n/a

 05-07-2008
On May 7, 11:39*am, Eric Sosman <(E-Mail Removed)> wrote:
> sophia wrote:
> > Dear all,

>
> > 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);
> > }

>
> * * *"How good" is a slippery question, because there are many
> criteria of goodness, some of them in conflict. *So I'll offer
> observations, not judgements.
>
> * * *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).
> Remember, each function invocation needs to "remember" where
> it was called from so it can return there. *The amount of space
> set aside for this bookkeeping is often rather limited, and if
> the recursive calls go too deep they may exhaust it.
>
> * * *3) You might gain some speed by handling the left branch
> (say) in a loop while making recursive calls only for the right
> branches.
>
> * * *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.
>
> * * *5) Adding `const' to the first argument might be nice.
>
> * * *6) Adding some commentary about what the function does and
> how to use it might be even nicer.
>
> * * *7) Passing a pointer to the totals array instead of using
> the global variable arrlev[] might be nice.
>
> - Show quoted text -

It would also be nice if the function reported the maximum depth
(the largest value of lev).
--
Fred Kleinschmidt

Guest
Posts: n/a

 05-08-2008
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.

--

Keith Thompson
Guest
Posts: n/a

 05-08-2008
Thad Smith <(E-Mail Removed)> 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.
(I'm probably not describing it very well.)

To attempt to describe the shape more precisely:

The root A has children B and C. (C has no children.)
B has children D and E. (E has no children.)
D has children F and G. (G has no children.)
F has children H and I. (I has no children.)
And so on.

And here's a picture (use a monospaced font):

A
/ \
B C
/ \
D E
/ \
F G
/ \
H I
.
.
.

> That doesn't fix the array bounds problem, though.

Right.

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Spiros Bousbouras
Guest
Posts: n/a

 05-08-2008
On 7 May, 19:16, sophia <(E-Mail Removed)> wrote:
> Dear all,
>
> 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);
>
> }

Apart from the comments made by others I note also
that the way it is written it will only count the nodes
starting from lev0 and above where lev0 is the value
it is initially passed as a second argument. I assume
the intention is to call the function with a second
argument of 0 but it might be clearer to write it like
this:

int arrlev[100];

void preorder(struct btree *n) {
preorder_aux(n , 0) ;
}

void preorder_aux(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);

}

I don't think the name "preorder" is very appropriate
because one would use it in cases where one might have
doubts that the preorder is actually an order. But a tree
is actually an order. Best to call your function
count_level_nodes or something.

Walter Roberson
Guest
Posts: n/a

 05-08-2008
In article <(E-Mail Removed)>,
Spiros Bousbouras <(E-Mail Removed)> wrote:

>I don't think the name "preorder" is very appropriate
>because one would use it in cases where one might have
>doubts that the preorder is actually an order. But a tree
>is actually an order. Best to call your function
>count_level_nodes or something.

I don't understand your comment, Spiros.

"preorder" is the name of one of the major strategies for
visiting all nodes of a tree; it involves visiting the leaves
of a node in left-to-right order, always following all the way down
the left-most unvisited side before processing any of the nodes further
right. The code the original poster put up uses preorder traversal
of a binary tree.

I have not been able to come up with a meaning of "order" that
would fit with your comment "But a tree is actually an order."
A tree just *is*; it might perhaps -encode- a command
("command" or "instructions" is one meaning of "order"), but
that would depend upon the -interpretation- of the tree, not upon
the tree itself.
--
"You may comand nature to the extent only in which you are willing to
obey her." -- Walter Russell

Spiros Bousbouras
Guest
Posts: n/a

 05-08-2008
On 8 May, 15:53, (E-Mail Removed)-cnrc.gc.ca (Walter Roberson) wrote:
> In article <(E-Mail Removed)>,
> Spiros Bousbouras <(E-Mail Removed)> wrote:
>
> >I don't think the name "preorder" is very appropriate
> >because one would use it in cases where one might have
> >doubts that the preorder is actually an order. But a tree
> >is actually an order. Best to call your function
> >count_level_nodes or something.

>
> I don't understand your comment, Spiros.
>
> "preorder" is the name of one of the major strategies for
> visiting all nodes of a tree; it involves visiting the leaves
> of a node in left-to-right order, always following all the way down
> the left-most unvisited side before processing any of the nodes further
> right. The code the original poster put up uses preorder traversal
> of a binary tree.
>
> I have not been able to come up with a meaning of "order" that
> would fit with your comment "But a tree is actually an order."
> A tree just *is*; it might perhaps -encode- a command
> ("command" or "instructions" is one meaning of "order"), but
> that would depend upon the -interpretation- of the tree, not upon
> the tree itself.

Oh I see. I was only familiar with the mathematical meaning of
preorder (http://en.wikipedia.org/wiki/Preorder) I didn't know it
also has a meaning in computer science. In the mathematical
sense a tree is a (partial) order which also makes it a preorder.

Guest
Posts: n/a

 05-17-2008
Keith Thompson wrote:
> Thad Smith <(E-Mail Removed)> 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.
> (I'm probably not describing it very well.)
>
> And here's a picture (use a monospaced font):
>
> A
> / \
> B C
> / \
> D E
> / \
> F G
> / \
> H I
> .
> .
> .
>

Oops, thanks for correcting my mistake.

--