Algorithm question: print all the elements on a single given level of a binary tree

Question

Hi, I am required to print out(visit) the nodes on a single level of a binary tree. I don't see how this can be done but then again I not very skilled with algorithms in general. I know that in Breadth-First traversal you use a queue and that you start by putting the root node in the queue then you dequeue it visit it and enqueue it's children and then you dequeue the first enqued child visit it and enqueue it's children and so on... And by my understanding this makes it impossible to know exactly when one level ends and another begins unless you assign each node it's level when the binary tree is created and then just check the level when you are doing the Breadth-First traversal.

Something like this(the code is in PHP but this is not a PHP related question it is a general algorithm related question - this is part of a function that adds a node to a binary tree storing the level in the node when each node is added):

if($this->root == null)
    {
        $this->root = $node;
                    $this->root->level = 1;
        return;
    }

    $nextnode = $this->root;

            $level = 1;

    while (true)
    {
        if($node->value > $nextnode->value)
        {
                        if($nextnode->right != null)
                        {
                            $nextnode = $nextnode->right;
                            $level++;
                        }
                        else
                        {
                            $nextnode->right = $node;
                            $nextnode->right->level = ++$level;
                            return;
                        }
        }
        else if($node->value < $nextnode->value) 
        {
                        if($nextnode->left != null)
                        {
                            $nextnode = $nextnode->left;
                            $level++;
                        }
                        else
                        {
                            $nextnode->left = $node;
                            $nextnode->left->level = ++$level;
                            return;
                        }
        }
        else if($node->value == $nextnode->value)
            return;
    }

So my question is:

Is this the only way of printing the nodes on a single level of a binary tree? Is there another way? Is there another way without storing the level when creating the tree?

Thank you in advance

Answer 1

Would a recursive solution suite you? I wrote this in C, i hope this is not a problem for you.

void traverse_tree_rec(TreeNode *ptn, int current_level, int targeted_level, (void*)(pVisit)(TreeElement*)){    
if (ptn==NULL)
    return;
else if(current_level == targeted_level)
    pVisit(ptn->entry);
else{
    traverse_tree_rec(ptn->left, current_level+1, targeted_level, pVisit);
    traverse_tree_rec(ptn->right, current_level+1, targeted_level, pVisit);
}

}

void traverse_level(Tree *pTree, int level, (void*)(pFunction)(TreeElement)){
traverse_level_rec(pTree->root, 0, level, pFunction);

}

Answer 2

This is so logical ... I feel stupid for not thinking about it before. Thank you. However this does not look like a very efficient means of doing it. You have to traverse the entire tree in order to find the nodes you wanted. Is there no other more efficent way?