Print all nodes at k distance from the root in a binary tree iteratively

Question

I am solving this interesting coding challenge of

printing all nodes at K distance from the root of a binary tree in a iterative fashion

Will be great to get review regarding how this code can be improved in a better way.

public class NodesAtKDistanceFromRoot {
 private final static Node EMPTY_MARKER = new Node(-1, null, null);
 public static void print(Node root, int level) {
 if (root == null) {
 return;
 }
 Deque<Node> queue = new ArrayDeque<>();
 int d = 1;
 queue.add(root);
 queue.add(EMPTY_MARKER);
 boolean found = false;
 while (!queue.isEmpty()) {
 Node current = queue.remove();
 if (current.equals(EMPTY_MARKER)) {
 // encountered empty marker which means all the nodes of a given level is visited
 d++;
 if (d == level) {
 found = true;
 break;
 } else {
 queue.add(EMPTY_MARKER);
 }
 } else {
 if (current.left != null)
 queue.add(current.left);
 if (current.right != null)
 queue.add(current.right);
 }
 }
 // print the nodes for the given level
 if (found) {
 while (!queue.isEmpty()) {
 Node current = queue.remove();
 System.out.println(current.val);
 }
 }
 }
}

Code in Github: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/tree/NodesAtKDistanceFromRoot.java

Answer 1

I think it's a decent implementation. It is readable and understandable. Nonetheless, I have some tips:

• Try to avoid single letter variable names, like d (unless in very specific cases like certain loop variables or mathematical constructs).

• Personally not a fan of new lines after each opening brace, it breaks the flow for me.

• Try to always use braces with if\while\... statements. It helps to prevent potential bugs.

• You could instead of silently returning, throw an (IllegalArgument\Nullpointer)Exception when passed node is null. Fail fast! Same with negative depths passed.

• Trivia: how would you print the root with your implementation?

I also do not think you need the marker. If you instead each loop execution only take all nodes present in the queue at the start of that loop, you will process all nodes level by level (but only use it if you have constant time size operations). As an example:

public static void print(Node root, int depth) {
 if (root == null) {
 return;
 }
 Deque<Node> queue = new ArrayDeque<>();
 queue.offer(root);
 while (!queue.isEmpty()) {
 boolean atRequiredDepth = --depth == 0;
 int nodeCount = queue.size();
 if (atRequiredDepth) {
 for (int i = 0; i < nodeCount; i++) {
 Node node = queue.poll();
 System.out.println(node.val);
 }
 return;
 } else {
 for (int i = 0; i < nodeCount; i++) {
 Node node = queue.poll();
 if (node.left != null) {
 queue.offer(node.left);
 }
 if (node.right != null) {
 queue.offer(node.right);
 }
 }
 }
 }
}

• Koekje: I am used to depth 0 being the root... :D