How to insert a node into a complete binary tree in Java?

Question

As we all know, when inserting into a complete binary tree we have to fill all the children for all the leafs from left to right. I have the following method that inserts a node into a complete binary tree.

//fields
private T item;
private int size;
private CBTree<T> left, right;

//add method
public void add(T item) 
{
    if(left == null)
    {
        left = new CBTree<T>(item);
        size += left.size;
    }
    else if(right == null)
    {
        right = new CBTree<T>(item);
        size += right.size;
    }
    else if(!((left.left != null) && (left.right != null)) && 
           ((right.left == null) || (right.right == null)))
    {
        left.add(item);
    }
    else
    {
        right.add(item);
    }
}

The problem with this implementation is that after the 11th node it adds the 12th node to the left child of 8 instead of 6. I understand that this is happening because the following line is reassigning the root of this tree to be the left child of the root.

left.add(item);

So it is changing the root to 2. Is there a way to change the root back to its original value? I am trying to accomplish this without using stacks and queues.

Answer 1

It's not sufficient to just check children of children to determine which side to go to, because as soon as the tree reaches height 4 that won't work any more, since children of children of the root won't change from that point forward yet we can still go either left or right.

2 approaches come to mind:

1. Have a complete variable at each node.

   A node with no children is complete.

   A node with 2 complete children of equal size is complete.

   Whenever update the tree (insert or delete) you update this variable for each affected node as well.

2. Mathematically determine whether a subtree is complete based on the size.

   A tree of size 2^n - 1 is complete (for some n).

   Note: this will only work if we're not allowed to freely delete elements without keeping the tree complete.

For either approach, when doing an insertion, we go left (left.add(item)) if either of these conditions are true:

• the left subtree is not complete
• the left and right subtrees are of the same size (both complete, meaning we're increasing the height with this insertion)

I'll leave the implementation details to you.

---

Note: you need to also update size when doing left.add(item); and right.add(item);. You could probably just stick a size++ in the add function, since we're adding 1 element so size increases by 1 no matter what.

Answer 2

Thanks to Dukeling's answer, the correct way to implement the method was to mathematically determine if the subtree was full. Here is the code:

//fields
private T item;
private int size;
private CBTree<T> left, right;

//add method
public void add(T item) 
{
    if(left == null)
    {
        left = new CBTree<T>(item);
    }
    else if(right == null)
    {
        right = new CBTree<T>(item);
    }
    else if(leftFull())
    {
        right.add(item);
    }
    else
    {
        left.add(item);
    }
    size++;
}

//Checks if the left subtree is full
public boolean leftFull()
{
    int used, leafs = 1;
    while(leafs <= size + 1)
    {
        leafs *= 2;
    }

    leafs /= 2;
    used = (size + 1) % leafs;
    if(used >= (leafs / 2))
    {
        return true;
    }
    else
    {
        return false;
    }
}