A complete Binary Search Tree with level order insert in Java

Question

We got an assignment where we need to code:

• A Binary Search Tree
• The Tree has to be complete, not perfect (which means all nodes which are not on the lowest level or second lowest level should have 2 children, while the nodes on the lowest level should be as far left as possible)
• We need to insert to the tree in level order

• So if I have an Array with elements {0, 1, 2, 3, 4, 5, 6, 7} the root should be 4, with 2, 1, 3, 0 on the left side, and 6, 5, 7 on the right side.

• The level order insert would be: 4, 2, 6, 1, 3, 5, 7, 0

• Just taking the middle of the Array and put it as root doesn't work. If you got an array of 1 to 9 elements, you would have 4 as root (int value in java, double would be 4.5), and you would have 5 elements on the right side, and 4 on the left side. This is not a complete tree. Not even a perfect tree.

My code is only able to insert at either left or right depending if it's greater og smaller than the root, no level order insertion. The Anytype x parameter is the value to be inserted, while the BinaryNode t is the current node we are at in the tree (that's how we compare if we need to insert the new value to the left or right)

private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
    if( t == null )
        return new BinaryNode<>( x, null, null );

    int compareResult = x.compareTo( t.element );

    if( compareResult < 0 )
        t.left = insert( x, t.left );
    else if( compareResult > 0 )
        t.right = insert( x, t.right );
    else
        ;  // Duplicate; do nothing
    return t;
}

How can I insert in level order and still maintain a binary search tree? Should I use some form of recursion?

My whole program

import java.nio.BufferUnderflowException;
import java.util.*;

import static java.lang.Math.pow;

/**
 * Implements an unbalanced binary search tree.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
    /**
     * Construct the tree.
     */
    public BinarySearchTree( )
    {
        root = null;
    }

    /**
     * Insert into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        root = insert( x, root );
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
    {
        if( t == null )
            return new BinaryNode<>( x, null, null );

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            t.left = insert( x, t.left );
        else if( compareResult > 0 )
            t.right = insert( x, t.right );
        else
            ;  // Duplicate; do nothing
        return t;
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the subtree.
     */
    private void printTree( BinaryNode<AnyType> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }

    /**
     * Internal method to compute height of a subtree.
     * @param t the node that roots the subtree.
     */
    private int height( BinaryNode<AnyType> t )
    {
        if( t == null )
            return -1;
        else
            return 1 + Math.max( height( t.left ), height( t.right ) );    
    }

    // Basic node stored in unbalanced binary search trees
    private static class BinaryNode<AnyType>
    {
            // Constructors
        BinaryNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
        }

        AnyType element;            // The data in the node
        BinaryNode<AnyType> left;   // Left child
        BinaryNode<AnyType> right;  // Right child
    }

      /** The tree root. */
    private BinaryNode<AnyType> root;

        // Test program
    public static void main( String [ ] args )
    {
        BinarySearchTree<Integer> t = new BinarySearchTree<>( );

        t.insert(2);
        t.insert(1);
        t.insert(3);
        t.printTree();
    }
}

Answer 1

I think you should do it this manner (code is in C#, but shouldn't be very hard to convert it to Java):

//list should be sorted
public void myFunc(List<int> list){
        Queue<List<int>> queue = new Queue<List<int>>();
         queue.Enqueue(list);

        while(queue.Any()){
            List<int> l = queue.Dequeue();
            int rindex = findRoot(l);
            //print r or store it somewhere
            Console.WriteLine(l.ElementAt(rindex));
            List<int> leftlist = l.GetRange(0, rindex);
            List<int> rightlist = l.GetRange(rindex + 1, l.Count-rindex-1);
            //leftlist = list l from index 0 to r-1; rightlist = list l from index r+1 to end.
            if (leftlist.Any())
            {
                queue.Enqueue(leftlist);
            }

            if (rightlist.Any())
            {
                queue.Enqueue(rightlist);
            }

        }

    }

******EDIT: *********************************************

For finding the root every time you have a list of size n, do the following:

public int findRoot(List<int> list)
        {
            int n = list.Count;

            double h = Math.Ceiling(Math.Log(n + 1, 2)) - 1;

            double totNodesInCompleteBinaryTreeOfHeighthMinusOne = Math.Pow(2, h) - 1;
            double nodesOnLastLevel = n - totNodesInCompleteBinaryTreeOfHeighthMinusOne;

            double nodesOnLastLevelInRightSubtree = 0;

            if (nodesOnLastLevel > Math.Pow(2, h - 1))
            {
                nodesOnLastLevelInRightSubtree = nodesOnLastLevel - Math.Pow(2, h - 1);
            }

            int rindex = (int)(n - nodesOnLastLevelInRightSubtree - 1 - ((totNodesInCompleteBinaryTreeOfHeighthMinusOne - 1) / 2));

            return rindex;
        }

Answer 2

The complete BST part took a bit of time to sort out what that actually is. Your requirement also calls for order level insert. I can't say this does "inserts", but it builds the BST in order level.

The input List must be sorted first.

The building in order level is accomplished by taking the root and adding it to the BST, then splitting what is left into left and right lists, adding them into a list of lists, then processing the list of lists. Each round of splitting and adding to a list of lists is a level of insertion.

The complete part is more difficult, as was noticed. The way to handle that is to compute the root for the list differently than a normal balanced tree. In a normal balanced tree the root index is at length/2. For the BST to be complete the root index has to be offset so that nodes that would normally appear on the right side of the root instead appear on the left side of the root. As long as the computation works for any length list then each split sublist is built properly.

From what I can tell computing the offset done by incrementing the offset for each additional element in length until you get to 1/2 of the width of a level. So, a BST with height of 4 has 8 elements in the lowest level. Lists of size 8, 9, 10, … 15 create BST with height of 4. For those lists the root index into the list is then 4, 5, 6, 7, 7, 7, 7, 7.

Seems to work.

public class Node<T extends Comparable<T>> {
    protected Node<T> left;
    protected Node<T> right;
    protected T data;   
}

public class BTree<T extends Comparable<T>> {
    private Node<T> root = new Node<>();
    public void addData(T data) {
        Node<T> parent = root;
        while (parent.data != null ) {
            if ( data.compareTo( parent.data ) > 0 ) {
                if ( parent.right == null ) 
                    parent.right = new Node<>();
                parent = parent.right;
            } else {
                if ( parent.left == null ) 
                    parent.left = new Node<>();
                parent = parent.left;
            }
        }
        parent.data = data;
    }
}

private void run() {
    for ( int i = 2; i < 65; ++i ) {
        List<Integer> intList = IntStream.range(1, i).boxed().collect(Collectors.toList());
        BTree<Integer> bTree = new BTree<>();
        List<List<Integer>> splitLists = new ArrayList<>();
        splitLists.add(intList);
        while (splitLists.size() > 0 ) {
            List<List<Integer>> tSplitLists = new ArrayList<>();
            for ( List<Integer> tIntList: splitLists) {
                int length = tIntList.size();
                // compute starting point
                int mid = calcMid(length);      // length/2 ; //+ calcOffset(length);
                bTree.addData(tIntList.get(mid));
                if ( mid - 0 > 0)
                    tSplitLists.add(tIntList.subList(0, mid));
                if ( length - (mid+1) > 0)
                    tSplitLists.add(tIntList.subList(mid+1, length));
            }
            splitLists = tSplitLists;
        }
        bTree.printNode();
    }
}
private int calcMid(int length) {
    if ( length <= 4 )
        return length / 2;
    int levelSize = 1;
    int total = 1;
    while ( total < length ) {
        levelSize *= 2;
        total += levelSize;
    }
    int excess = length - (total - levelSize);
    int minMid = (total - levelSize + 1) / 2;
    if ( excess <= levelSize / 2 ) {
        return minMid + (excess - 1); 
    } else {
        int midExcess = levelSize/2; 
        return minMid + (midExcess - 1);
    }

}

See How to print binary tree diagram? for code on printing a binary tree.

PS> I'm sure you can make it a bit better by clearing and copying Lists instead of making new ones each time.

EDIT: Did you go and get the printNode code referenced above?

1 

 2   
/   
1   

 2   
/ \ 
1 3

   3       
  / \   
 /   \  
 2   4   
/       
1

And so on …