Solved

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

Posted on 1998-08-04
12
263 Views
Last Modified: 2010-04-10
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...
0
Comment
Question by:spike55
  • 5
  • 4
  • 2
  • +1
12 Comments
 

Author Comment

by:spike55
ID: 1169424
Edited text of question
0
 
LVL 3

Expert Comment

by:xyu
ID: 1169425
Send more details about internal structure of the tree... on abstraction level that You described the task I'm not sure there is any effective algorithm to do that... actually if You bin-search tree node has structure like
  struct TNode {
    ...
    TNode* pLeft;
    TNode* pRight;
  } ...
it possible only using some additional storage... like that...

You creating array of size equal to Tree height (for binary search tree like RB-tree or AVL-Tree its not bigger than 2*log2(TreeSize). Each element of the array is queue of the node pointers. Now You doing preorder on the tree counting current level number and inqueuing node pointer into queue with index equal to current level... than you can walk through resulting data-structure :) any way You want.
Note: Working (almoust commercial) example of AVL-Tree implementetion is at "http:\\come.to\okthinks" (Natlib Class Library)...


0
 
LVL 3

Expert Comment

by:xyu
ID: 1169426
Addition:
   preorder have to be realized like that:

   
   // can be static member of the function or member of the
   // class or even one of the params of the recursion
   //--------------------------------------------------------
   size_t nLevel = 0;

   // size is the height of the tree. If You going to
   // use Natlib the vector is self growing
   //---------------------------------------------------------
   TVectorOf< TVectorOf<TNode*> > aa_Levels[...];

   //---------------------------------------------------------
   void CollectByLevels(const TNode* pc_Node)
   {
     aaLevels[nLevel].Insert(pc_Node);
     ++nLevel;
     if (pc_Node->pLeft) Preorder(pc_Node->pLeft);
     if (pc_Node->pRight) Preorder(pc_Node->pRight);
     --nLevel;
   } /*CollectByLevels(const TNode*)*/

   Preorder(Tree.pRoot);
 
   or

   //---------------------------------------------------------
   void CollectByLevels(const TNode* pc_Node, size_t nLevel)
   {
     aaLevels[nLevel].Insert(pc_Node);
     if (pc_Node->pLeft) Preorder(pc_Node->pLeft, nLevel + 1);
     if (pc_Node->pRight) Preorder(pc_Node->pRight, nLevel + 1);
   } /*CollectByLevels(const TNode*, size_t)*/

   CollectByLevels(Tree.pRoot, 0);

0
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 
LVL 22

Expert Comment

by:nietod
ID: 1169427
This is surely for an assignment.  We CANNOT provide answers to assignments.  We can provide assistance in about the same way your professor would.  That is we can answer specific questions and we can look overy your work and over limited suggestions.)

Unethical behavior, either by the client asking the question or the expert answering,  is grounds for removal from EE.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1169428
As far as i can tell, xyu, has not given you ans answer that meets your assignment requirements.  (I'm having a hard time following it.)

I can.  If you would like HELP, I will ASSIST you in meeting your assignment.  I will not give you the answer.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1169429
Now I understand xyu's code.  That is definitely not what the assignment asked for.  xyu's approach will work, but is different and less efficient.
0
 

Expert Comment

by:jeseem
ID: 1169430
spkie55
what u have given ac lagorithm is breadth first search for graph (not binary search tree).
If u want it just for binary search tree
instead      for each unvisited node
   just say   for leftchild and for rightchild.if they exist.
for queue implementation why not use linked list.
0
 
LVL 3

Expert Comment

by:xyu
ID: 1169431
to nietod!
About efficiency of the solution...
the execution time of it is O(TreeSize)
the memory requirements is about sizeof(void*) * TreeSize + C, where C is size of vector implementation;

I'm not sure there are any reasons to extend size of the Node structure to hold additional information like Is Visited or Pointer To Sibling Node... it can take even more space... and cleaning of these fields an take some time ... imagine that You need to perform iteration more than once... More than that if You already have implementation of the tree from 3d parties :) and don't want to go and change it (or unable to do that) what can be Your idea?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1169432
The idea presented in the question can be used to do a level order traversal  with less memory requirements than yours.  You build a data structure that stores pointers to every node in three.  That is ever node of every level is stored.  Correct?  The question doesn't ask for it that way.  It stores less than 2 levels as a time.  For a big tree this is a big savings.  In additon it visits the nodes more efficiently.

>>I'm not sure there are any reasons to extend size of the Node
>> structure to hold additional information like IsVisited
>> or PointerToSiblingNode

that's not part of the algrithm.  You don't need the IsVisited to get this accomplished, that is requested in the question probably as a way to test that the algrithm is working.  You definitly don't need a pointer to the subling node in a binary tree.  There are trees where that is good to have, but not for this task or for a binary tree.
0
 
LVL 3

Expert Comment

by:xyu
ID: 1169433
to nietod.. ok i got it..
sorry
0
 

Author Comment

by:spike55
ID: 1169434
Releasing this question for Nietod only...
0
 
LVL 22

Accepted Solution

by:
nietod earned 300 total points
ID: 1169435
Thanks.
0

Featured Post

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

813 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now