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.