Find all nodes in a binary tree on a specific level (Interview Query)

algorithm, binary-tree, breadth-first-search

Solution

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

Initial invocation would look like: `drill (root, 0, n, rqueue);`

Problem

I mean on a specific level, NOT up to that specific level. Could someone please check my modified BFS algorithm? (most of which is 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) } } } ```

Original source