Question
Write a method called completeToLevel that accepts an integer n as a parameter and that adds nodes to a tree to complete the first n levels. A level is complete if every possible node at that level is not null . We will use the convention that the overall root is at level 1 , its children are at level 2 , and so on. You should preserve any existing nodes in the tree. Any new nodes added to the tree should contain the value –1. Your method should throw an IllegalArgumentException if it is passed a value for a level that is less than 1.
For example, if a variable called t refers to reference tree #2 and you make the call of t.completeToLevel(4); , the tree should change to the following tree:
Add the above method to the IntTree class from this chapter. You may define additional private methods to implement your public method if necessary. Several problem descriptions refer to the following reference binary trees:
Answer
public void completeToLevel(int n)
{
if(n < 1)
throw new IllegalArgumentException();
if(overallRoot == null && n == 1)
{
overallRoot = new IntTreeNode(-1);
}
else if(overallRoot == null && n >= 1)
{
overallRoot = new IntTreeNode(-1);
completeToLevel(overallRoot, n - 2);
}
else
{
completeToLevel(overallRoot, n - 2);
}
}
private void completeToLevel(IntTreeNode root, int n)
{
if(overallRoot.left == null)
{
overallRoot.left = new IntTreeNode(-1);
}
if(overallRoot.right == null)
{
overallRoot.right = new IntTreeNode(-1);
}
if(root.left != null && n > 0)
{
if(root.left.left == null)
{
root.left.left = new IntTreeNode(-1);
}
if(root.left.right == null)
{
root.left.right = new IntTreeNode(-1);
}
completeToLevel(root.left, n - 1);
}
if(root.right != null && n > 0)
{
if(root.right.left == null)
{
root.right.left = new IntTreeNode(-1);
}
if(root.right.right == null)
{
root.right.right = new IntTreeNode(-1);
}
completeToLevel(root.right, n - 1);
}
}