level order binary search
Author Message
level order binary search

What is the algorithm for a level order search of a binary tree?
Knuth leaves it as an "exercise for the reader".  Peachy.

Thanks, Ed

Tue, 15 Sep 1998 03:00:00 GMT
level order binary search

Quote:

>What is the algorithm for a level order search of a binary tree?
>Knuth leaves it as an "exercise for the reader".  Peachy.

>Thanks, Ed

A level order traverse (or search) looks at the root, then all
nodes at level 2, then all nodes at level 3, and so on. In general
a node at level k is processed after all nodes at level k-1 and
before all nodes at level k+1.

The algorithm to do this is the following:

Put the root node in a queue.
while the queue is not empty
remove a node from the queue and process it.
put the children of the node just processed in the queue.
end while

This is similar to the usual pre, in, and post order traversals
except that a queue is used instead of a stack.

Tue, 15 Sep 1998 03:00:00 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages