BST Level Traversal

Question

Ok, so I'm trying to do a level order traversal of a binary search tree and its not working. The code below makes sense to me, but that is probably because I've been looking at it forever and I've convinced myself that it should work.

void BST<T>::levelByLevel(ostream &out) { 
 Queue<BinNodePointer> q; 
 BinNodePointer subtreeRoot; 

 if(myRoot == NULL) 
  return; 
 q.enqueue(myRoot); 
 while(!q.empty()) {
  subtreeRoot = q.front(); 
  out << subtreeRoot->data << " "; 
  q.dequeue(); 

  if(subtreeRoot->left != NULL) 
   q.enqueue(subtreeRoot->left); 
  if(subtreeRoot->right != NULL) 
   q.enqueue(subtreeRoot->right); 
 } 
}

Maybe you guys could point out what I'm doing wrong because, although I understand the concept of a binary search tree, I'm not 100% on all the ins and outs.

Well, if I enter something like this into the tree: 12 24 18.. the output of the level traversal is: 12 24 18.. which is not correct. The output I was expecting is 24 12 18 — Dalton Conley, May 02 '10 at 23:08
Is `BST<>` an AVL? If not then your expectation is wrong. This input would yield a tree that has three levels. If the tree is ordered by left-is-bigger then you should get a tree like this: root is 12, its left child is 24 and its right child is NULL; the left child of 24 is NULL and the right child of 24 is 18. — wilhelmtell, May 02 '10 at 23:16

score 1 · Accepted Answer · answered May 02 '10 at 23:22

There is nothing wrong with the result.

Can you explain how do you arrive at 24,12,18 ?

I assume you insert 12 first at root level, then you insert 24 which ends up as right node of root 12 then you insert 18 which ends up as left node of 24 - because 18 is bigger then root 12 so going right, then 18 is less then 24 so it is inserted as right node of 24

So:

So you have 3 levels, level 1 (12), level 2 (24), level 3 (18) so level traversal 12,24,18 as your algorithm is inserting.

ahh thank you! It makes more sense.. in fact if I would have just drew it out I would have probably came to the same conclusion. My issue is, its from a lab manual and I've concluded the displaying of a tree is incorrect. — Dalton Conley, May 02 '10 at 23:42

BST Level Traversal

1 Answers1