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

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


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

"""
Explanation: <small><i>This notebook was prepared by Donne Martin. Source and license info is on GitHub.</i></small>
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
End of explanation
"""


%run ../tree_height/height.py

# %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()

"""
Explanation: Unit Test
The following unit test is expected to fail until you solve the challenge.
End of explanation
"""


