Given a binary search tree and a level, calculate the number of nodes at that level

Question

The problem statement is in the title. If the given tree is empty, -1 is returned. If the tree has k levels, and the given level is m, and m> k, -2 is returned. If neither of these conditions is met, the number of levels is returned.

Here is my implementation in Java and some JUnit tests. The code is also available on GitHub.

Node

package ru.maksim.nodecountbylevel.api;
class Node {
 private final int key;
 private Node left;
 private Node right;
 Node(int key) {
 this.key = key;
 }
 void setLeft(Node left) {
 this.left = left;
 }
 void setRight(Node right) {
 this.right = right;
 }
 int getKey() {
 return key;
 }
 Node getLeft() {
 return left;
 }
 Node getRight() {
 return right;
 }
 @Override
 public String toString() {
 return Integer.toString(key);
 }
}

BinarySearchTree

package ru.maksim.nodecountbylevel.api;
public class BinarySearchTree {
 private Node root = null;
 private int size = 0;
 public BinarySearchTree(int... keys) {
 insertAll(keys);
 }
 Node getRoot() {
 return root;
 }
 public void insertAll(int... keys) {
 for (int key : keys) {
 insert(key);
 }
 }
 public void insert(int key) {
 if (root == null) {
 root = new Node(key);
 } else {
 Node current = root;
 Node parent = null;
 while (current != null) {
 parent = current;
 current = (key < current.getKey()) ? current.getLeft() : current.getRight();
 }
 if (key < parent.getKey()) {
 parent.setLeft(new Node(key));
 } else {
 parent.setRight(new Node(key));
 }
 }
 size++;
 }
 public boolean isEmpty() {
 return size == 0;
 }
}

TreeAlgorithms

package ru.maksim.nodecountbylevel.api;
import com.sun.istack.internal.NotNull;
import java.util.ArrayDeque;
import java.util.Queue;
 public class TreeAlgorithms {
 private static final Node END_OF_LEVEL = new Node(0);
 public static final int TREE_EMPTY = -1;
 public static final int NO_SUCH_LEVEL = -2;
 private TreeAlgorithms() {
 throw new AssertionError();
 }
 public static int getNodeCountByLevel(@NotNull BinarySearchTree tree, final int level) {
 if (level < 0) {
 throw new IllegalArgumentException("level cannot be negative");
 }
 if (tree.isEmpty()) {
 return TREE_EMPTY;
 }
 Queue<Node> nodes = new ArrayDeque<>();
 nodes.add(tree.getRoot());
 nodes.add(END_OF_LEVEL);
 int currentLevel = 0;
 while (currentLevel < level) {
 Node node = nodes.remove();
 if (node == END_OF_LEVEL) {
 nodes.add(END_OF_LEVEL);
 currentLevel++;
 continue;
 }
 Node left = node.getLeft();
 if (left != null) {
 nodes.add(left);
 }
 Node right = node.getRight();
 if (right != null) {
 nodes.add(right);
 }
 if (nodes.size() == 1) {
 return NO_SUCH_LEVEL;
 }
 }
 return nodes.size() - 1;
 }
 }

JUnit tests.

package ru.maksim.nodecountbylevel.api;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;
public class TreeAlgorithmsTest {
 @Test
 void assertEmptyTree() {
 BinarySearchTree tree = new BinarySearchTree();
 assertEquals(TreeAlgorithms.TREE_EMPTY, TreeAlgorithms.getNodeCountByLevel(tree, 0));
 }
 @Test
 void assertRootOnly() {
 BinarySearchTree tree = new BinarySearchTree(1);
 assertEquals(1, TreeAlgorithms.getNodeCountByLevel(tree, 0));
 }
 @Test
 void assertFirstLevelIncomplete() {
 BinarySearchTree tree = new BinarySearchTree(1, 2);
 assertEquals(1, TreeAlgorithms.getNodeCountByLevel(tree, 1));
 }
 @Test
 void assertFirstLevelComplete() {
 BinarySearchTree tree = new BinarySearchTree(2, 1, 3);
 assertEquals(2, TreeAlgorithms.getNodeCountByLevel(tree, 1));
 }
 @Test
 void assertSecondLevelIncomplete() {
 BinarySearchTree tree = new BinarySearchTree(10, 4, 16, 2, 7, 12);
 assertEquals(3, TreeAlgorithms.getNodeCountByLevel(tree, 2));
 }
 @Test
 void assertLevelGreaterThanTreeHas() {
 BinarySearchTree tree = new BinarySearchTree(10, 4, 16, 2, 7, 12);
 assertEquals(TreeAlgorithms.NO_SUCH_LEVEL, TreeAlgorithms.getNodeCountByLevel(tree, 20));
 }
 @Test
 void assertNegativeLevelPassed() {
 BinarySearchTree tree = new BinarySearchTree(10, 4, 16, 2, 7, 12);
 assertThrows(
 IllegalArgumentException.class,
 () -> TreeAlgorithms.getNodeCountByLevel(tree, -1)
 );
 }
}

Answer 1

If the given tree is empty, -1 is returned. If the tree has k levels, and the given level is m, and m> k, -2 is returned.

Are these specs given our self imposed? If the latter, I suggest changing them.

• The requested level should be>= 1, otherwise throw an illegal argument exception
• In an empty tree, there are 0 levels, so a valid requested level will always be bigger than the number of levels. So I think it makes sense to use the same return value regardless of the tree being empty or not
• How many nodes are at a level higher than the tree? Naturally 0. I think that should be the return value. And notice that there is no other case where 0 will be the return value, so this captures well the case of too high request.

It's interesting what you did with END_OF_LEVEL to track the ends of levels. I think a simpler technique is to use nodes.size() to achieve the same. Something like this:

while (currentLevel < level) {
 int count = nodes.size();
 for (int i = 0; i < count; i++) {
 Node node = nodes.poll();
 // add children ...
 }
}
return currentLevel == level ? nodes.size() : 0;

• Maksim Dmitriev: the requested level should be >= 0 (not 1). The root is at level 0

Answer 2

• Using private static final Node END_OF_LEVEL = new Node(0); as a sentinel means that the client can't have 0 as a key ever. It is a very strong restriction, and if you mean it you must enforce it, or at least document it.

• An if (level < 0) test strongly suggests that level should really be an unsigned int.

• An unrestricted access to private members (e.g. left and right) via getters and setters is as (削除) bad (削除ここまで) good as making them public.

• Maksim Dmitriev: There is no unsigned int in Java