no :of nodes

S

sophia

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

Walter Roberson

sophia said:
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);
 
F

fred.l.kleinschmidt

sophia said:
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).
 
T

Thad Smith

Eric said:
sophia said:
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.
 
K

Keith Thompson

Thad Smith said:
[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.
 
S

Spiros Bousbouras

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.
 
W

Walter Roberson

Spiros Bousbouras said:
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.
 
S

Spiros Bousbouras

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.
 
T

Thad Smith

Keith said:
Thad Smith said:
Eric said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top