Find all nodes in a binary tree at a certain level (Interview Query)

Question

I mean at a certain level, NOT to a certain level. Can anyone check my modified BFS algorithm? (most of which are taken from Wikipedia)

Queue levelorder(root, levelRequested){ int currentLevel = 0; q = empty queue  q.enqueue(root)  while not q.empty do{    if(currentLevel==levelRequested) return q; node := q.dequeue()    visit(node) if(node.left!=null || node.right!=null){ currentLevel++;    if node.left ≠ null      q.enqueue(node.left)    if node.right ≠ null      q.enqueue(node.right) } } } 

Answer 1

I think a recursive solution would be much more concise:

 /* * node - node being visited * clevel - current level * rlevel - requested level * result - result queue */ drill (node, clevel, rlevel, result) { if (clevel == rlevel) { result.enqueue (node); else { if (node.left != null) drill (node.left, clevel + 1, rlevel, result); if (node.right != null) drill (node.right, clevel + 1, rlevel, result); } } 

The initial call will look like this: drill (root, 0, n, rqueue);

Answer 2

The problem with your algorithm is that nodes, all on the same level, mistakenly increase the number of levels.

Explanation:

• Set root level to 0

• When you add nodes at any level, set their level to 1 higher than the level of their parent.

• As soon as you get any node that has a level number equal to the required level number, it simply breaks out of the BFS and discard all the nodes in the queue behind the current node that have the same level number.

See the comment for more details.

Here is one solution:

 void Tree::printSameLevel(int requiredLevel) { queue BFSQ; TreeNode * temp; BFSQ.push(getHead()); while(!BFSQ.empty()) { temp = BFSQ.front(); BFSQ.pop(); //if the level of the current node is equal to the //required level, we can stop processing now and simply //remove from the queue all the elements that follow //and have the same level number. //It follows from properties of BFS that such elements //will occur in a series ( level by level traversal). if(temp->level == requiredLevel) { break; } if(temp->right) { BFSQ.push(temp->right); temp->right->level = temp->level + 1; } if(temp->left) { BFSQ.push(temp->left); temp->left->level = temp->level + 1; } } if(!BFSQ.empty() || requiredLevel==0) { cout << "Printing all the nodes at level " << requiredLevel << " : "; while(temp&&temp->level == requiredLevel) { cout << temp->data << " "; temp = BFSQ.front(); BFSQ.pop(); } } } 

Here is an example output:

  5 7 3 8 6 4 2 TREE STATS _____________________ Inorder Trace = 2 3 4 5 6 7 8 Height = 2 Internal Nodes = 3 Leaf Nodes = 4 Total Nodes = 7 _____________________ Trees printed above are mirrors! Printing all the nodes at level 0 : 5 Printing all the nodes at level 1 : 7 3 

If you're interested, I added a function to the implementation of common roles here . You will find a large number of tree operations for reference (mirror, height, beautiful printing, etc.).