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

Solution Notebook

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

Constraints
Test Cases
Algorithm
Code
Unit Test

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

To create a bst with minimum height, we need to use the middle element as the root. We'll use recursion to divide the array in half and continue to pick the middle element from the left and right halves as the nodes to insert in the tree.

create_min_bst(array, start, end)
Base case: Stop when end < start
Create a node with the mid element
Recursively build node.left by calling create_min_bst using the left sub array
Recursively build node.right by calling create_min_bst using the right sub array
Return the node

Complexity:

Time: O(n)
Space: O(h), where h is the tree's height (since this is a tree with minimum height, h = log n)

Code



In [1]:

    
%run ../bst/bst.py



In [2]:

    
from __future__ import division


def create_min_bst(array):
    if array is None:
        return
    return __create_min_bst__(array, 0, len(array)-1)


def __create_min_bst__(array, start, end):
    if end < start:
        return
    mid = (start + end) // 2
    node = Node(array[mid])
    node.left = __create_min_bst__(array, start, mid-1)
    node.right = __create_min_bst__(array, mid+1, end)
    return node

Unit Test



In [3]:

    
%run ../tree_height/height.py



In [4]:

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









    



Overwriting test_bst_min.py



In [5]:

    
%run -i test_bst_min.py









    



Success: test_bst_min