Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Creating Binary Search Trees

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?

like image 813
Tobi3 Avatar asked May 11 '12 11:05

Tobi3


2 Answers

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.

like image 137
Nate Kohl Avatar answered Sep 24 '22 01:09

Nate Kohl


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
like image 35
hugomg Avatar answered Sep 25 '22 01:09

hugomg