Runnung time of the level order traversal

[APEJMAN]

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?

void Tree<T> :: level_order_traversal(std::ostream& out, TreeNode<T>*
 rootNode)
{
 
    Queue <TreeNode<T>*> queue;
 
    int dep; //depth of the node
    int temp=0;
    queue.enter(root);
    while (!queue.isEmpty()) {
        rootNode = queue.leave();
        if( depth(rootNode)!=temp){
        temp=depth(rootNode);
        out<<"\n";
        }
 
        out<<rootNode->data<<" ";
 
        if (rootNode->left!= NULL)
            queue.enter(rootNode->left);
 
        if (rootNode->right != NULL){
            queue.enter(rootNode->right);
        }
    }
 
 
} 

[sicarie]

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?

[APEJMAN]

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?

[sicarie]

What does your textbook/notes/teacher say about how to calculate the run time?

[APEJMAN]

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

[sicarie]

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?

[APEJMAN]

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

[sicarie]

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?

[Ganon11]

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?