Find root that will always make a complete Binary Search Tree

Question

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:

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

"How can I make a method that knows this?" Isn't that the question you're supposed to answer as your homework/test/whatever? What process have you followed so far to solve this puzzle? What ideas have you tried and discarded? — Dave Newton, Oct 10 '18 at 16:24
I have used 2 weeks on this and I can't find the solution. Now I am seeking help for ideas to how to make it. I have tried lots and lots of different things that didn't work, what's the point of posting them if they don't work? — , Oct 10 '18 at 16:25
So we *know* you actually tried. And you may have been closer than you thought. How would you do it if you had to do it manually? If you know the definition of "complete binary tree" and can create one on paper, then you can create one through code, once you've generalized the solution. So make you some trees for great good. — Dave Newton, Oct 10 '18 at 16:29
It's not that simple no. To do it on paper is not the same as "just" doing it in code. I need to find the root first (which is what I am asking here), then I would need to find out what element I should insert to the left, which wouldn't just be 1 (the smallest element), then I would need to find the one to insert to the right and so on. Like a Level order insertion. — , Oct 10 '18 at 16:31
Yes, it *is* that simple: that's what algorithm research is. Doing examples and generalizing. BTW, if you'd just search the web for this you'd find the cheats you seek--I found multiple implementations quite easily. — Dave Newton, Oct 10 '18 at 16:33
I can guarantee you, that you haven't found any solution to a Complete Binary Search Tree. I have searched the whole web. There are lots of implementations for a Complete Binary Tree, not a search tree, there are 0 — , Oct 10 '18 at 16:34
That's a decidedly odd claim to make, but ok. (BTW, the ones I didn't find were in C and Java, so should be portable to whichever language you're targeting.) Guess it's impossible! Good luck! — Dave Newton, Oct 10 '18 at 16:37
It's not odd, I know what I am talking about, there are no Complete Binary Search Tree implementations anywhere. The ones you found are Complete Binary Tree. I am 101% sure :) — , Oct 10 '18 at 16:38
Cool! Glad you know what you're talking about! Should make implementing it much easier. — Dave Newton, Oct 10 '18 at 16:39
Feel free to link the Complete Binary Search tree you found, and let me tell you why it's not a Complete Binary Search Tree :) — , Oct 10 '18 at 16:41
Nah, I'm good; I'll let you do this one on your own. Again: pencil and paper are your best friend. I'll try a clean-room implementation tomorrow night (first chance I'll have) for grins. — Dave Newton, Oct 10 '18 at 17:21

Roman Posokhin · Answer 1 · 2018-10-10T17:54:11.530

2

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

edited Oct 10 '18 at 17:54

answered Oct 10 '18 at 17:23

Roman Posokhin

78
4

What is - th element – Oct 10 '18 at 17:26
So let's see your example: K = 9, N = 4. Last level contains 2 elements, so does last level. So root element is 2^(4 - 2) + (9 - 2^(4 - 1) + 1) = 6 – Roman Posokhin Oct 10 '18 at 17:27
@mth1417 I mean order (rank). If tree contains numbers from 1 to K then root will be exactly ans = 2^(N-2) + C+1. If it's not, it will be ans-th element in ascending order – Roman Posokhin Oct 10 '18 at 17:29
Yes but this would require me to know the amount of levels right? :) the method can't know that before all elements have been inserted into the tree. But I would need the root before inserting all the other elements. – Oct 10 '18 at 17:29
@mth1417 If you know number of elements that you're going to insert into the tree, you can easily get number of tree levels – Roman Posokhin Oct 10 '18 at 17:32
If I do it with K being 6, so 6 elements in the tree, it gives 5 as root, whereas 4 should be root: 2^(3-2) + (6 - 2^(3-1) + 1) = 5 – Oct 10 '18 at 17:41
@mth1417 You missed max() expression that helps if the last level is filled more than the half. So answer will be 2^(N-2) + 2^(N-2) = 4 – Roman Posokhin Oct 10 '18 at 17:56
Hmm. That is very complicated isn't it? To find out when the last level is filled more than half or not. – Oct 10 '18 at 18:08
I mean it's complicated coding it, how would the method know that – Oct 10 '18 at 18:09
@mth1417 no, it's not. You don't even try it by yourself, just ask me question by question. It was pretty much easier for me to provide you complete implementation, but I'm not going to. You should just apply logarithm to number of elements to get number of levels. Please mark my answer as solution because I gave you what you want and spend much time for explanation – Roman Posokhin Oct 11 '18 at 03:15
@mth1417 actually, `Math.ceil(K+1)` will find you number of levels and Math.min() will help you to get number of elements on the last level of the left subtree. Please mark my contribution as well. – Roman Posokhin Oct 11 '18 at 03:23
I am indeed trying what you are saying or else I wouldn't have found all the flaws in you answer, which you have changed like 7 times now. Thanks for your help, but using 3 formulas to find levels, find left half of last level, and finding right half of last level is complicated. – Oct 11 '18 at 04:46
@mth1417 did you expect two-row-algorithm for the problem that you have been unsuccessfully trying to solve last couple of weeks? What do you mean by "complicated" if 3 formulas is just 3 local variables? – Roman Posokhin Oct 11 '18 at 05:01
No I did not, there is just no need for 3 formulas. I have uploaded the solution. – Oct 11 '18 at 13:46

score 1 · Accepted Answer · edited Oct 11 '18 at 21:41

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

score -2 · Answer 3 · answered Oct 10 '18 at 16:30

-2

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

answered Oct 10 '18 at 16:30

Roman Posokhin

78
4

Yes but a self balancing Tree is not a complete tree :) – Oct 10 '18 at 16:32
@mth1417 What exactly is complete binary tree in your opinion? Do you mean the where the distances from root to every leaf are the same? – Roman Posokhin Oct 10 '18 at 16:38
No. A complete binary tree is a tree where all nodes have 2 children except the second last and last level, which can have 0-2 children. All the children should be as far as left as possible, like the one in my post. If you look at the one in my post, and for example insert 10 to the right of 9, it would not be complete because it's not as far left as possible. To be far left as possible, the next number should be to the left of 5. – Oct 10 '18 at 16:40
@mth1417 ok. added another answer. Mark as solution if it's the thing you asked for. – Roman Posokhin Oct 10 '18 at 16:59
I was reading your answer but it vanished, I cannot find it :) – Oct 10 '18 at 17:06
@mth1417 I realised I was wrong. Posted again, check that out – Roman Posokhin Oct 10 '18 at 17:24

Find root that will always make a complete Binary Search Tree

3 Answers3