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
- What's wrong with the
getDepthmethod because it seems that it returns 4 levels instead of 3? - 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.