Creating Binary Search Trees

Question

If i construct a binary search tree adding the following values in order:

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

I get a tree of height 5. Is there a method (other than trial and error) that I can use to determine an ordering of the integers that would create a tree of height 4?

Auricula

You need the Balancing Binary Tree – Matrilateral

possible duplicate of Balancing a Binary Tree (AVL) – Elsy

I am not looking to construct a balanced tree as such, more determine an ordering of the integers that would get a height of 4. – Auricula

Answer 1

I haven't thought this through completely, but one way of getting a tree of specific depth is to sort your elements before inserting them: i.e. sorting then inserting N elements into a binary search tree will produce a tree of depth N.

You might be able to:

1. Sort your elements
2. Insert a specific K=4 of them to produce a tree of depth K
3. Insert the remaining elements in such a way that the tree doesn't get deeper.

(Of course, choosing which K elements to start with and a strategy for inserting the remaining elements is the tricky part -- but maybe this would be a start?)

---

Edit: I think a general solution is possible, assuming K is big enough. How about this:

1. Given 10, 7, 16, 12, 5, 11, 2, 20, 1, 14
2. Sort your elements: 1, 2, 5, 7, 10, 11, 12, 14, 16, 20
3. Insert the last K=4 elements, then the last K-1, then K-2, and so on, down to 1.

For example, after sorting and inserting the last 4:

12
  \
   14
     \
      16
        \
         20

...then after inserting the last 3:

  12
 /  \
7    14
 \     \
  10    16
    \     \
     11    20

...then after the last 2:

    12
   /  \
  7    14
 / \     \
2   10    16
 \    \     \
  5    11    20

...and finally, after inserting the last element:

      12
     /  \
    7    14
   / \     \
  2   10    16
 / \    \     \
1   5    11    20

...you're left with a BST of height K=4.

Note that this approach will only work when K is big enough -- specifically, when K(K+1)/2 >= N.

Needlepoint

Where do you get the 18 in the binary tree? – Danuloff

@Chibox: sorry, typo. Should be fixed now. – Needlepoint

I don't think your method works on all cases. Say we have a tree with the numbers 1-7. If we use your method we insert 5,6,7 then 3,4 then 2, then 1. The final result is a tree of height 4 with 5 as the root node. However, its possible to arrange 7 nodes as a perfectly balanced binary tree with height 3, if we use 4 as the root node. – Kurbash

@missingno: true, this approach only works when K is big enough. I've updated the answer. – Needlepoint

@NateKohl: No, your approach will always have a counter example. The example I gave of a perfectly filled tre with 2^h - 1 elements extends to all h as well. We know that there is only one way to have this dense tree to stay balanced and in order to do that you need the larger half of the elements to include the root node and the (densily packed) right subtree. If you insert them in order like you suggested you end up with just a spine and it will not be enough. – Kurbash

@missingno: I'm confused -- what does balancing have to do with the OPs question? Can you give an example N and K, where K*(K+1)/2 >= N, where the above approach will fail to produce a BST of height K? – Needlepoint

I think I get it now: I was thinking the OP wanted a perfectly balanced tree (since 4 is the smallest heigth we can get with those elements) while you interpreted him as if you receive K as a separate input that can be "suboptimal" – Kurbash

@NateKohl if I have 7 elements, I cant build a BST in height 2 or 3 for example? – Bedazzle

@OfirAttia: you could definitely build a BST with height 3 (not height 2) to hold 7 elements, but not using this approach. – Needlepoint

@NateKohl you have link to some information about that? for example I want to order 2,5,6,11,17,18,22 In heights of 2,3,4,5,6 , what approach I need to use to do that? Thanks. – Bedazzle

Answer 2

Yes, you can first construct a perfectly balanced tree and you can then output the nodes in a way that has the parent nodes being printed before their children.

To create a perfectly balanced tree, just sort the numbers and then use recursive binary divisions to build a tree.

---

For example, in your case we would sort the numbers

 1 2 5 7 10 11 12 14 16 20

and then build a balanced tree from them (take the middle number as the root and repeat this process recursively)

            11
     5            14
 1     7       12    16
   2     10             20

We can now use a preorder traversal or a breadth-first traversal to print the nodes in an order you want (as long as we output the parent nodes before the children we will be fine).

11 5 14 1 7 12 16 2 10 20

Kurbash

Answer 3

public void testMakeBinarySearchTree() {
    List<Integer> array = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        array.add(i+1);
    }


    Collections.shuffle(array);


    Node root = new Node(array.get(5));
    for (int value : array) {
        binarySearchTreeInsertNode(root, value);
    }
}


private void binarySearchTreeInsertNode(Node node, int value) {
    int data = node.getData();
    if ( value > data) {
        Node right = node.getRight();
        if (right != null) {
            binarySearchTreeInsertNode(right, value);
        } else {
            node.setRight(new Node(value));
        }
    } else if (value < data) {
        Node left = node.getLeft();
        if (left != null) {
            binarySearchTreeInsertNode(left, value);
        } else {
            node.setLeft(new Node(value));
        }
    }
}

Obliquely