CODEWITHSUNDEEP
javabinary-treebinary-search-tree
user7722505
user7722505

Reputation:

Find root that will always make a complete Binary Search Tree

I need to make a Complete Binary Search Tree. If I have a method that looks like this:

public void createCompleteTree(Node n, int i)

And I for example use the number 9 as the i value, what do I do to find a root that will make a complete tree?

If I use 9 as the value, the numbers would be 1,2,3,4,5,6,7,8,9. For a complete Binary search tree, the root must be 6, like below:

enter image description here

How can I make a method that knows this? It should work with any kind of number, so if I want to use number 14 it should be able to.

So far the only code I have is an insert method, which just checks if the number to be inserted is greater (goes to the right) or smaller (goes to the left) than the node we are currently at. x is the number to be inserted, t is the current node we are at in the tree:

 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;
}

Upvotes: 0

Views: 1117

Answers (3)

user7722505
user7722505

Reputation:

This is the solution:

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

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);
   }
}

Found as part of this code:

https://stackoverflow.com/a/52749727/9899617

Upvotes: 1

Roman Posokhin
Roman Posokhin

Reputation: 78

Binary tree with N levels may contain from 2^(N-1) to 2^N - 1 element.
Last (lowest) level of tree that you describe may contain from 1 to 2^(N-1) elements in the strict order.
Tree with K elements and N levels contains K - 2^(N-1) + 1 elements on its last level. Left subtree of this tree contains C = min(K - 2^(N-1) + 1, 2^(N-2)) elements. So root of tree will be 2^(N-2) + C -th element

Upvotes: 2

Roman Posokhin
Roman Posokhin

Reputation: 78

Root of your binary tree does not have to be constant. There exists self-balancing trees. Check this out: enter link description here

Upvotes: -2

Related Questions