This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Challenge Notebook

Problem: Create a binary search tree with minimal height from a sorted array.

Constraints
Test Cases
Algorithm
Code
Unit Test
Solution Notebook

Constraints

Is the array in increasing order?
- Yes
Are the array elements unique?
- Yes
Can we assume we already have a Node class with an insert method?
- Yes

Test Cases

0, 1, 2, 3, 4, 5, 6 -> height 3
0, 1, 2, 3, 4, 5, 6, 7 -> height 4

Algorithm

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

Code



In [ ]:

    
%run ../bst/bst.py
%load ../bst/bst.py



In [ ]:

    
def create_min_bst(array):
    # TODO: Implement me
    # Calls __create_min_bst__
    pass    


def __create_min_bst__(array, start, end):
    # TODO: Implement me
    pass

Unit Test

The following unit test is expected to fail until you solve the challenge.



In [ ]:

    
%run ../tree_height/height.py



In [ ]:

    
# %load test_bst_min.py
from nose.tools import assert_equal


class TestBstMin(object):

    def test_bst_min(self):
        array = [0, 1, 2, 3, 4, 5, 6]
        root = create_min_bst(array)
        assert_equal(height(root), 3)

        array = [0, 1, 2, 3, 4, 5, 6, 7]
        root = create_min_bst(array)
        assert_equal(height(root), 4)

        print('Success: test_bst_min')


def main():
    test = TestBstMin()
    test.test_bst_min()


if __name__ == '__main__':
    main()

Solution Notebook

Review the Solution Notebook for a discussion on algorithms and code solutions.