Print all the elements on a single given level of a binary tree

I am required to print out(visit) th开发者_如何学Pythone 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 questions are:

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?

---

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);
}

---

@Para,

this makes it impossible to know exactly when one level ends and another begins unless ....

You need not traverse the whole tree during the BFS traversal you are trying to do. You can modify the BFS psedocode given in wiki by introducing an array level[]; You have to do these:

1. initialize level as 0 for each node.

2. whenever u mark o in line: o ← G.opposite(t,e) assign level[o] = level[t]+1;

3. after t ← Q.dequeue() if level[t] > targeted_level break;