473,388 Members | 1,153 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,388 software developers and data experts.

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

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

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

Similar topics

2
by: Christopher | last post by:
I have a hash that is several levels deep. ie: 'vars' => { '$filers' => '10.10.10.10/32', '$networksa' => '10.10.10.10/32', '$networksb' => '10.50.0.0/16', '$wintel_boxes' =>...
1
by: mike | last post by:
best regards: What is the difference between DOM Level 1 and DOM Level 2. Thank you. May god be with you.
1
by: guy001 | last post by:
Hi, I'm trying to traverse the DOM in a bit of a non-traditional manner and am struggling to get my head around it. Just say i have some elements like so: A |-B |-C | |-D |
11
by: james | last post by:
In SQL Server there is @@NESTLEVEL which returns the current number of levels down in a recursive function call. Is there a C# equivilant to get the current level of a recursive method call? I...
6
by: GrispernMix | last post by:
//ques and and level order traversal file name: lab6_build_leaf_up.cpp Instructions:
7
by: GrispernMix | last post by:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h> #include <iostream> #include <string.h> using namespace std; #define TRUE 1 #define FALSE 0
33
by: desktop | last post by:
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is a pointer to an element can be done in amortized constant time. I guess that is not worst case since std::set is...
6
by: APEJMAN | last post by:
would you please help me? I wrote 3 separate line of code for printing my binary tree, and now I am trying to print the level-order traversal of the tree, where the nodes at each level of the tree...
4
by: APEJMAN | last post by:
would you please help me with this question? I know that a binary tree can be recovered from its pre-order traversal. That is, a tree built from the pre-order traversal should always be the same as...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.