A straightforward recursive level-order traversal method?

Question

I have seen answers indicating that there is something intrinsically non-recursive about level-order traversal. I suggest it can be done recursively in a very natural way (Node is defined as expected) :

static void printKids(List<Node> kids) {
     List<Node> newKids = new ArrayList<>();
     for (var k : kids) {
         System.out.print(" "+k.data+" ");
         if (k.left != null) newKids.add(k.left);
         if (k.right != null) newKids.add(k.right);
     }
     System.out.println("\n");
     if (newKids.size() > 0) printKids(newKids);
 }

Is this inefficient or hard to understand? The one somewhat awkward thing is that rather than taking a node as its argument (like the root node of a tree) it takes a list of nodes, but that seems like a minor problem.

Answer 1

This code is fine, but the use of recursion really comes down to tail recursion. But as Java (in which you coded it) does not implement tail-call elimination, this uses call stack space that really is not necessary.

You've effectively replaced a loop with a tail recursive call, while most would prefer to do the opposite to so save the memory use of the stack.