no :of nodes

Discussion in 'C Programming' started by sophia, May 7, 2008.

  1. sophia

    sophia Guest

    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);
    }
    sophia, May 7, 2008
    #1
    1. Advertising

  2. In article <>,
    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]++;


    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
    Walter Roberson, May 7, 2008
    #2
    1. Advertising

  3. sophia

    Guest

    On May 7, 11:39 am, Eric Sosman <> 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
    , May 7, 2008
    #3
  4. sophia

    Thad Smith Guest

    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
    Thad Smith, May 8, 2008
    #4
  5. Thad Smith <> 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) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, May 8, 2008
    #5
  6. On 7 May, 19:16, 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);
    >
    > }


    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.
    Spiros Bousbouras, May 8, 2008
    #6
  7. In article <>,
    Spiros Bousbouras <> 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
    Walter Roberson, May 8, 2008
    #7
  8. On 8 May, 15:53, -cnrc.gc.ca (Walter Roberson) wrote:
    > In article <>,
    > Spiros Bousbouras <> 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.
    Spiros Bousbouras, May 8, 2008
    #8
  9. sophia

    Thad Smith Guest

    Keith Thompson wrote:
    > Thad Smith <> 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.

    --
    Thad
    Thad Smith, May 17, 2008
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. asd
    Replies:
    3
    Views:
    425
    Arnaud Berger
    May 23, 2005
  2. gavnosis
    Replies:
    0
    Views:
    498
    gavnosis
    Aug 2, 2003
  3. Timo Nentwig

    selecting nodes between other nodes

    Timo Nentwig, Jun 16, 2004, in forum: XML
    Replies:
    1
    Views:
    390
    Patrick TJ McPhee
    Jun 17, 2004
  4. Johnny Ooi

    Looking A Nodes From Within Nodes

    Johnny Ooi, Nov 13, 2004, in forum: XML
    Replies:
    10
    Views:
    642
    Johnny Ooi
    Nov 14, 2004
  5. Replies:
    2
    Views:
    376
Loading...

Share This Page