Solved

# Need a function to do a level order traversal of a binary tree

Posted on 1998-08-04

Pretty urgent- I need a class member function to do a level by level traversal of a binary search tree. All the books I have give recursive code for in-, pre- and post-order traversal, but this seems rather different (and is iterative) I found a pseudocode version of a level-order graph traversal, but it leaves out the problem I am having- how to move from the node you are on to the adjacent one and so on down the tree. The pseudocode function I have is:

Assume a binary tree with n levels

Each node contains a boolean variable "visited"

Binary class has a member function to mark visited TRUE

Using a basic queue, which has a NotEmpty function that returns TRUE/FALSE.

Start at the root node

Enqueue the value in the root node

while (Queue not empty)

{

Dequeue first value

for (each unvisited node adjacent to the the current node)

{

Mark node as visited

Enqueue value in current node

} // end for

} // end while

That for loop condition is just a bit vague!! Like I said, my problem is how to move thru the tree. I could hard code for a set number of levels, but obviously this is not acceptable. So I need a fairly specific function, although you are free to use whatever (descriptive) names you want for any member/helper functions or pointers needed. I just need to be able to see what the function would do. I suspect though that it mainly requires pointer manipulations. I have the code for the bst, queue, etc, just need this one function...