level order traversal of binary tree

Discussion in 'C Programming' started by sophia.agnes@gmail.com, Feb 14, 2008.

  1. Guest

    Dear all,

    How good is this function which implements level order traversal of
    binary tree ?

    level_trav(struct node *sn)
    {
    struct node *queue[MAX];
    int front = rear = -1;

    front++;
    rear++;
    queue[rear] = sn;

    while(front <= rear)
    {
    sn = queue[front++];
    if(sn != NULL)
    {
    printf("%d",sn -> val);
    queue[++rear] = sn -> left;
    queue[++rear] = sn -> right;
    }
    }
    }
    , Feb 14, 2008
    #1
    1. Advertising

  2. writes:

    > How good is this function which implements level order traversal of
    > binary tree ?


    These are just coding comments rather than algorithmic ones...

    > level_trav(struct node *sn)
    > {
    > struct node *queue[MAX];
    > int front = rear = -1;
    >
    > front++;
    > rear++;


    Looks odd. Just initialise both to 0.

    > queue[rear] = sn;
    >
    > while(front <= rear)
    > {
    > sn = queue[front++];
    > if(sn != NULL)
    > {
    > printf("%d",sn -> val);
    > queue[++rear] = sn -> left;
    > queue[++rear] = sn -> right;


    I'd want to check that there is room!

    > }
    > }
    > }


    Mildly algorithmic points:

    - You will be able to handle bigger trees if you don't queue up NULL
    pointers rather than testing for them when you de-queue.

    - Again, you get better usage from your array if you make your queue
    circular.

    --
    Ben.
    Ben Bacarisse, Feb 14, 2008
    #2
    1. Advertising

  3. On Thu, 14 Feb 2008 06:01:40 -0800 (PST),
    wrote:

    >Dear all,
    >
    >How good is this function which implements level order traversal of
    >binary tree ?
    >
    >level_trav(struct node *sn)
    >{
    > struct node *queue[MAX];
    > int front = rear = -1;


    This doesn't define rear so it remains undefined throughout your
    program.

    >
    > front++;
    > rear++;
    > queue[rear] = sn;
    >
    > while(front <= rear)
    > {
    > sn = queue[front++];
    > if(sn != NULL)
    > {
    > printf("%d",sn -> val);
    > queue[++rear] = sn -> left;
    > queue[++rear] = sn -> right;
    > }
    > }
    > }



    Remove del for email

    --
    Posted via a free Usenet account from http://www.teranews.com
    Barry Schwarz, Feb 15, 2008
    #3
  4. Kaz Kylheku Guest

    On Feb 14, 6:01 am, wrote:
    > Dear all,
    >
    > How good is this function which implements level order traversal of
    > binary tree ?
    >
    > level_trav(struct node *sn)
    > {
    >   struct node *queue[MAX];


    This queue is allocated in automatic storage, and is used to simulate
    a stack. So effectively, your program is recursive.

    >   int front = rear = -1;


    This declaration declares only front. Where is rear? If you don't have
    rear as a global variable somewhere, this is an error.

    Before you post something, at least try to compile it and fix as many
    errors as you are able.

    C declarations do not have this multiple = syntax for declaring
    multiple identifiers; you must write:

    int front = -1, rear = -1;

    Or perhaps:

    int front = -1, rear = front;


    >   front++;
    >   rear++;


    What's the point of this? Why initialize two variables to -1 when your
    very next step overwrites their value with the successor? Just take
    this out and change the initialization to:

    int front = 0, rear = 0;

    No???

    >   queue[rear] = sn;
    >
    >   while(front <= rear)
    >   {
    >      sn = queue[front++];
    >      if(sn != NULL)
    >      {
    >        printf("%d",sn -> val);
    >        queue[++rear] = sn -> left;
    >        queue[++rear] = sn -> right;
    >      }
    >    }
    >  }


    You have a few problems. Firstly, why not make the queue circular? The
    way you have it, once you visit a node at position queue[N], you never
    reuse that position. So your queue needs as many entries as the total
    number of nodes in the tree.

    Secondly, you are wasting lots of space by storing null pointers in
    the queue when encountering leaf nodes. If sn->left is null, there is
    no point in doing queue[++rear] = sn->left. You're just placing a null
    pointer into the path, which your (sn != NULL) test has to stumble
    over later. And it means that your queue has to be sized to handle all
    of the null pointers in the leaves. Are you not aware that there are
    more null pointers in the leaf nodes of the tree than there are nodes
    in the tree?

    For instance, consider a simple two level tree:

    A
    B C

    It has three nodes, okay? The children B and C each have two null
    pointers. That's four null pointers. And four is, like, more than
    three, get it? Try it with a deeper tree:

    A
    B C
    D E F G

    Now there are seven nodes, right? How many null pointers? Yes, eight.
    Each of D E F C has two. Again eight is greater than seven. Always one
    more than the number of nodes. Each level has as many items in it as
    all of the levels before it, plus one. Level 1 has A. Level two has B
    C, one more than A. Level 3 has D E F G (four items), one more than
    levels 1 and 2 combined (three items).

    This is why if you make your queue circular, you need only about half
    the space. The most space will be needed when you are doing the bottom
    level, and that has only half the total number of nodes. As you
    prepare that level by queuing it at the tail, you are removing the
    previous level, visiting those nodes, and that space can be used.
    Kaz Kylheku, Feb 15, 2008
    #4
  5. Kaz Kylheku Guest

    On Feb 14, 6:01 am, wrote:
    > Dear all,
    >
    > How good is this function which implements level order traversal of
    > binary tree ?


    I have another comment about this. The queue-based algorithm needs a
    queue proportional to the sizeo of the tree. Effectively you are doing
    a breadth first search.

    A breadth first search can be made to require less space by using a
    depth-first search instead, and using repeated depth-first searches
    to /fake/ the effect of a breadth-first search.

    This is done by repeatedly doing a breadth-first search whose depth is
    limited, and iteratively increasing the depth. This is called
    iterative deepening.

    First you do a depth-first search which only goes to depth 0. Then you
    do another one which goes to depth 1. Then you do one which goes to
    depth 2, and so on.

    Whenever you hit the bottom depth, you visit the nodes at that depth.

    The storage you require is proportional to the depth of the tree, not
    the number of nodes in it, and it can be done recursively.


    /*
    * helper function: visit nodes at specified depth.
    * return 1 if something was visited, otherwise 0.
    */

    static int visit_depth(struct node *node, int depth)
    {
    if (node != NULL) {
    int left_visited, right_visited;

    if (depth == 0) {
    printf("%d\n", node->val);
    return 1;
    }

    left_visited = visit_level(node->left, depth - 1);
    right_visited = visit_level(node->right, depth - 1);
    return left_visited || right_visited;
    }
    return 0;
    }

    [[Student exercise question: above, why didn't we write

    return visit_level(node->left, level - 1) || visit_level(node-
    >right, level - 1);


    and instead used the left_visited and right_visited variables?]]



    Now given visit_depth above, we can simply write level_trav like this:

    void level_trav(struct node *tree)
    {
    int depth;

    /* keep increasing depth until no nodes are found at that depth */

    for (depth = 0; visit_level(tree, depth); depth++)
    {
    /* empty */
    }
    }

    Now you might think that the algoithm is slow because it keeps
    revisiting the lower depths over and over again. But remember that
    more than half of the nodes are in the bottom-most level that is
    visited. Each time visit_level is called with a greater depth, it
    visists more than twice as many nodes as in the previous iteration.
    And this means that in the last iteration, it visits about as many
    nodes as in all of the first iterations combined! This means that half
    of the work is always in the last iteration! So the algorithm runs in
    O(N) and basically the overhead for doing it this way is that you
    traverse each node twice on average. Of course, the nodes at the
    bottom level are visited only once (and that's more than half the
    nodes in the tree!). And the root node is a high traffic corridor,
    being a gateway to the rest of the tree: it is traversed in each
    iteration.

    Whether you want to do it this way or using the queue depends on how
    large the tree is. Can you spare the O(N) queue storage? Or the tree
    large enough that saving memory is worth traversing the nodes more
    than once?
    Kaz Kylheku, Feb 15, 2008
    #5
    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. GrispernMix

    ques and and level order traversal

    GrispernMix, Dec 2, 2006, in forum: C Programming
    Replies:
    6
    Views:
    465
    GrispernMix
    Dec 3, 2006
  2. GrispernMix
    Replies:
    7
    Views:
    482
    David Harmon
    Dec 3, 2006
  3. Replies:
    9
    Views:
    4,898
  4. Christian Rühl
    Replies:
    22
    Views:
    1,720
    Christian Rühl
    Dec 13, 2007
  5. Vijay Meena
    Replies:
    1
    Views:
    1,922
    red floyd
    Nov 30, 2008
Loading...

Share This Page