1
\$\begingroup\$

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)
        );
    }
}
\$\endgroup\$
2
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ the requested level should be >= 0 (not 1). The root is at level 0 \$\endgroup\$ – Maksim Dmitriev Jul 6 '17 at 7:33
2
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ There is no unsigned int in Java \$\endgroup\$ – Maksim Dmitriev Jul 6 '17 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.