This notebook was prepared by Donne Martin. Source and license info is on GitHub.
We'll use a recursive solution that validates left <= current < right, passing down the min and max values as we do a depth-first traversal.
Complexity:
%run ../bst/bst.py
import sys
class BstValidate(Bst):
def validate(self):
if self.root is None:
raise TypeError('No root node')
return self._validate(self.root)
def _validate(self, node, minimum=-sys.maxsize, maximum=sys.maxsize):
if node is None:
return True
if node.data <= minimum or node.data > maximum:
return False
if not self._validate(node.left, minimum, node.data):
return False
if not self._validate(node.right, node.data, maximum):
return False
return True
%%writefile 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()
Overwriting test_bst_validate.py
%run -i test_bst_validate.py
Success: test_bst_validate