This notebook was prepared by Donne Martin. Source and license info is on GitHub.
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.
%run ../bst/bst.py
%load ../bst/bst.py
class MinBst(object):
def create_min_bst(self, array):
# TODO: Implement me
The following unit test is expected to fail until you solve the challenge.
# %load test_bst_min.py
import unittest
def height(node):
if node is None:
return 0
return 1 + max(height(node.left),
height(node.right))
class TestBstMin(unittest.TestCase):
def test_bst_min(self):
min_bst = MinBst()
array = [0, 1, 2, 3, 4, 5, 6]
root = min_bst.create_min_bst(array)
self.assertEqual(height(root), 3)
min_bst = MinBst()
array = [0, 1, 2, 3, 4, 5, 6, 7]
root = min_bst.create_min_bst(array)
self.assertEqual(height(root), 4)
print('Success: test_bst_min')
def main():
test = TestBstMin()
test.test_bst_min()
if __name__ == '__main__':
main()
Review the Solution Notebook for a discussion on algorithms and code solutions.