468,504 Members | 1,985 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,504 developers. It's quick & easy.

Runnung time of the level order traversal

33
hI
Would you please help me with this question?
Using Big O Notation, what is the running time of the level-order traversal ( the code below) in terms of the number of nodes N and the tree height h? Based on your knowledge of the possible values of h, what are the average, best, and worst running times in terms of just N? would you please explain to me?

Expand|Select|Wrap|Line Numbers
  1. void Tree<T> :: level_order_traversal(std::ostream& out, TreeNode<T>*
  2.  rootNode)
  3. {
  4.  
  5.     Queue <TreeNode<T>*> queue;
  6.  
  7.     int dep; //depth of the node
  8.     int temp=0;
  9.     queue.enter(root);
  10.     while (!queue.isEmpty()) {
  11.         rootNode = queue.leave();
  12.         if( depth(rootNode)!=temp){
  13.         temp=depth(rootNode);
  14.         out<<"\n";
  15.         }
  16.  
  17.         out<<rootNode->data<<" ";
  18.  
  19.         if (rootNode->left!= NULL)
  20.             queue.enter(rootNode->left);
  21.  
  22.         if (rootNode->right != NULL){
  23.             queue.enter(rootNode->right);
  24.         }
  25.     }
  26.  
  27.  
Feb 29 '08 #1
8 3897
sicarie
4,677 Expert Mod 4TB
APEJMAN-

You're obviously in a class advanced enough to have covered these concepts, so what do you think? Did you create a program with it and calculate the depth?
Feb 29 '08 #2
APEJMAN
33
APEJMAN-

You're obviously in a class advanced enough to have covered these concepts, so what do you think? Did you create a program with it and calculate the depth?
Here is the concept of the program:
a program that allows the user to enter their own integer-valued binary search tree (BST). The program ask the user to first enter the number of nodes N they want in the tree. Then the user will type in their values, in the order they should be inserted in the tree. Finally, your program should report the following:

The maximum value and its depth in the tree.
The minimum value and its depth in the tree.
The height of the tree.
The in-order, pre-order, and post-order traversals of the tree. Modify the tree traversals to print the values separated by spaces rather than line breaks, as shown in the screenshot below.
The level-order traversal of the tree, where the nodes at each level of the tree are printed on a separate line.

so, I wrote the Program
But I have no Idea how to calculate the Running time.

Would you please help me?
Feb 29 '08 #3
sicarie
4,677 Expert Mod 4TB
What does your textbook/notes/teacher say about how to calculate the run time?
Feb 29 '08 #4
APEJMAN
33
for example a for loop, like for(int i=0;i<=n;i++)
a code like this has a running time of O(N)
but what about my while loop on a tree? is it ( N Log(N) ) that's what I figured out
Feb 29 '08 #5
sicarie
4,677 Expert Mod 4TB
for example a for loop, like for(int i=0;i<=n;i++)
a code like this has a running time of O(N)
but what about my while loop on a tree? is it ( N Log(N) ) that's what I figured out
Okay, well, I think part of your confusion is that you are trying to answer your question in just one whack. You're actually asked a few different questions - best, worst, and average. So the methodology on calculating each of those is different. So the question is, how did you get O(n log(n) )? Is that best, worst, or average case for traversal time?
Feb 29 '08 #6
APEJMAN
33
Okay, well, I think part of your confusion is that you are trying to answer your question in just one whack. You're actually asked a few different questions - best, worst, and average. So the methodology on calculating each of those is different. So the question is, how did you get O(n log(n) )? Is that best, worst, or average case for traversal time?
I believe that it would be the average running time.
would you please help me? I'm totally confused.
Thanks
Feb 29 '08 #7
sicarie
4,677 Expert Mod 4TB
Sorry, had to run out yesterday. That looks right to me (please, anyone else if I'm wrong, speak up).

So what are you confused at with finding that? Or does your confusing come in finding best and worst case traversals?
Mar 1 '08 #8
Ganon11
3,652 Expert 2GB
I'm not so sure it's n log n. Think about it - No matter what, each node in your tree will enter the queue only once, and so they will only be processed once. What's the running time when each of N items gets processed once, taking constant time for each processing?
Mar 1 '08 #9

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

1 post views Thread by guy001 | last post: by
6 posts views Thread by GrispernMix | last post: by
7 posts views Thread by GrispernMix | last post: by
4 posts views Thread by APEJMAN | last post: by
reply views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.