level order traversal of binary tree

[sophia.agnes]

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

 

[Ben Bacarisse]

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.

 

[Barry Schwarz]

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

 

[Kaz Kylheku]

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]

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?