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?

Solution 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.

Solution 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