Creating Java binary search tree

Question

So here is the Node class:

public class Node
{
    private int _info;
    private Node _left;
    private Node _right;

    public Node()
    {
        //this._info = Integer.MIN_VALUE;
        this._left = null;
        this._right = null;
    }


    public int getInfo()
    {
        return _info;
    }

    public void setInfo(int _info)
    {
        this._info = _info;
    }

    public Node getLeft()
    {
        return _left;
    }

    public void setLeft(Node _left)
    {
        this._left = _left;
    }

    public Node getRight()
    {
        return _right;
    }

    public void setRight(Node _right)
    {
        this._right = _right;
    }  
}

How I create the tree:

public class BalancedBinaryTree
{
    private ArrayList<Integer> _numbers;
    private Node _root;

    public BalancedBinaryTree(ArrayList<Integer> numbers)
    {
        this._numbers = new ArrayList<>();
        this._numbers.addAll(numbers);
        Collections.sort(this._numbers);

        this._root = new Node();

        this.create(this._root, 0, this._numbers.size());
    }

    private void create(Node tree, int i, int j)
    {
        if (i < j)
        {
            int m = i + (j - i) / 2;

            tree.setInfo(this._numbers.get(m));

            tree.setLeft(new Node());
            create(tree.getLeft(), i, m);

            tree.setRight(new Node());
            create(tree.getRight(), m + 1, j);
        }
    }

This method computes the depth:

    public static int getDepth(Node node)
    {
        if (node == null)
        {
            return 0;
        }
        else
        {
            int max = 0;
            if (getDepth(node.getLeft()) > getDepth(node.getRight()))
            {
                max = getDepth(node.getLeft());
            }
            else
            {
                max = getDepth(node.getRight());
            }
            return max + 1;
        }
    }

And these two combined should print the tree by its levels:

    public static void printLevel(Node node, int levelToDisplay, int currentLevel)
    {
        if (node != null)
        {
            printLevel(node.getLeft(), levelToDisplay, currentLevel);
            if (currentLevel == levelToDisplay)
            {
                System.out.print(node.getInfo() + " ");
            }
            currentLevel++;
            printLevel(node.getRight(), levelToDisplay, currentLevel);
        }
    }

    public static void printLevels(Node node)
    {
        for (int i = 0; i < getDepth(node); i++)
        {
            System.out.println("Level :" + i);
            printLevel(node, i, 0);
            System.out.println();
        }
    }

In a test class I have:

    testNumbers.add(15);
    testNumbers.add(20);
    testNumbers.add(25);
    testNumbers.add(30);
    testNumbers.add(35);
    testNumbers.add(40);
    testNumbers.add(45);


    BalancedBinaryTree tree = new BalancedBinaryTree(testNumbers);
    BalancedBinaryTree.printLevels(tree.getRoot());

And I get this output:

Level :0
0 15 20 30 
Level :1
0 0 25 0 35 40 
Level :2
0 0 0 45 
Level :3
0

I should get

Level :0
30
Level :1
20 40
Level :2
15 25 35 45

1. What's wrong with the getDepth method because it seems that it returns 4 levels instead of 3?
2. Why are there additional nodes? (those zeroes)

I'm pretty sure I solved the problems but I will need an explanation for the following:

This is the modified printlevel method:

public static void printLevel(Node node, int levelToDisplay, int currentLevel)
{
    if (node.getLeft() != null && node.getRight() != null)           
    {
        printLevel(node.getLeft(), levelToDisplay, currentLevel+1);  
        if (currentLevel == levelToDisplay)
        {
            System.out.print(node.getInfo() + " ");
        }
        printLevel(node.getRight(), levelToDisplay, currentLevel+1);  
    }
}

As you can see I test now if the current node has childs instead of checking if the current node exists and this is why those zeroes appeard because the traversal reached the leafs that had no info assigned on their right and left childs.

The thing I want to understand is the difference between incrementing currentLevel and then passing it to the call of printLevel and simply passing currentLevel+1 to the call. Shouldn't it be the same thing ?

And the getDepth function:

public static int getDepth(Node node)
{
    if (node.getLeft() == null && node.getRight() == null)
    {
        return 0;
    }
    else
    {
        int max = 0;
        if (getDepth(node.getLeft()) > getDepth(node.getRight()))
        {
            max = getDepth(node.getLeft());
        }
        else
        {
            max = getDepth(node.getRight());
        }
        return 1 + max;
    }
}

Same thing here: traversal reached the leafs and got one more call for its childs thus returning one additional level so again, the solution is to test if the current node has childs instead of checking if the current node exits.

Answer 1

What's wrong with the getDepth method because it seems that it returns 4 levels instead of 3?

From your print method it seems, that you number the levels from 0 to n (the root of a tree beeing 0). Your getDepth method however will never return 0. Two things: if (node != null) this check does not seem to make very much sense. Null does not seem to be an allowed input (as the root is constructed on construction of a Tree). If this is the case (and you do want to check it) an exception might be more appropriate. The main problem seems to be this: return max + 1; So the minimal value returned is 0 + 1, which is 1.

As a small sidenote: I would save the values of the two recursive calls of getDepth, it would greatly increase performance. Also, if you do use short variable names such as i, m or j (in a non-loop index kind of way) it would be helpful to document their meaning.

And conserning your first question: tree.setLeft(new Node()); What would be the value of this Node as of now? And what will happen if the i < j codition in the recurive call will not pass? If you can answer those questions, you should be able to fix the code yourself.