Creating Binary Search Trees
algorithm, binary-search, binary-tree
Solution
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:
- Sort your elements
- Insert a specific `K=4` of them to produce a tree of depth `K`
- 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:
- Given `10, 7, 16, 12, 5, 11, 2, 20, 1, 14`
- Sort your elements: `1, 2, 5, 7, 10, 11, 12, 14, 16, 20`
- 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`.
Problem
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?