473,388 Members | 1,153 Online

# Runnung time of the level order traversal

33
hI
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 4167
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.

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.
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