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.

• releseabe: Thanks, something to consider and I read now that implementing this is, not surprisingly or I guess they would have tail-call elimination already, non-trivial. My goal was to provide the simplest (most understandable) code possible to do level-order traversal.
• trincot: Some readers my find the recursive version easier, while (many?) others will better understand the loop. That is a matter of taste and option, so I just focused on the objective assessment about memory use.
• releseabe: The queue stuff seemed "tricky" to me; but I can understand some feeling the same way about recursion, here and perhaps in general.
• trincot: BTW, others have mentioned a recursive implementation of BFS before: see here and also on Stack Overflow. Once you realise that a loop can be replaced by a tail recursive call, it really isn't that much different. And also an iterative version can use a stack instead of queue if you wanted to (and I often do): it means you have a nested loop that starts with a new stack at each iteration of the outer loop.