This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

Problem: Determine if a tree is a valid binary search tree.

Constraints

  • Can the tree have duplicates?
    • Yes
  • If this is called on a None input, should we raise an exception?
    • Yes
  • Can we assume we already have a Node class?
    • Yes
  • Can we assume this fits in memory?
    • Yes

Test Cases

None -> exception

Valid:
      5
    /   \
   5     8
  /     /
 4     6
        \
         7

Invalid:
      5
    /   \
   5     8
    \   
    20

Algorithm

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.

  • If the node is None, return True
  • If min is set and the node's value <= min, return False
  • if max is set and the node's value > max, return False
  • Recursively call the validate function on node.left, updating max
  • Recursively call the validate function on node.right, updating min

Complexity:

  • Time: O(n)
  • Space: O(h), where h is the height of the tree

Code

In [1]:
%run ../bst/bst.py
In [2]:
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

Unit Test

In [3]:
%%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
In [4]:
%run -i test_bst_validate.py
Success: test_bst_validate