This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Valid: 5 / \ 5 8 / / 4 6 \ 7 Invalid: 5 / \ 5 8 / \ / 4 9 7
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 BstValidate(Bst):
def validate(self):
# TODO: Implement me
pass
The following unit test is expected to fail until you solve the challenge.
# %load test_bst_validate.py
import unittest
class TestBstValidate(unittest.TestCase):
def test_bst_validate_empty(self):
bst = BstValidate(None)
bst.validate()
def test_bst_validate(self):
bst = BstValidate(Node(5))
bst.insert(8)
bst.insert(5)
bst.insert(6)
bst.insert(4)
bst.insert(7)
self.assertEqual(bst.validate(), True)
bst = BstValidate(Node(5))
left = Node(5)
right = Node(8)
invalid = Node(20)
bst.root.left = left
bst.root.right = right
bst.root.left.right = invalid
self.assertEqual(bst.validate(), False)
print('Success: test_bst_validate')
def main():
test = TestBstValidate()
test.assertRaises(TypeError, test.test_bst_validate_empty)
test.test_bst_validate()
if __name__ == '__main__':
main()
Review the Solution Notebook for a discussion on algorithms and code solutions.