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: Determine if a tree is a valid binary search tree.

Constraints
Test Cases
Algorithm
Code
Unit Test

Constraints

Can the tree have duplicates?
- Yes
Can we assume we already have a Node class?
- Yes

Test Cases

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

Invalid:
      5
    /   \
   5     8
    \   
    20

Algorithm

We'll use a recursive solution that valides left <= current < right, passing down the min and max values as we do a depth-first traversal.

If the node is None, return False
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]:

    
def validate_bst(node):
    return __validate_bst__(node, None, None)


def __validate_bst__(node, mininum, maximum):
    if node is None:
        return True
    if mininum is not None and node.data <= mininum:
        return False
    if maximum is not None and node.data > maximum:
        return False
    if not __validate_bst__(node.left, mininum, node.data):
        return False
    if not __validate_bst__(node.right, node.data, maximum):
        return False
    return True

Unit Test



In [3]:

    
%%writefile test_bst_validate.py
from nose.tools import assert_equal


class TestBstValidate(object):

    def test_bst_validate(self):
        node = Node(5)
        insert(node, 8)
        insert(node, 5)
        insert(node, 6)
        insert(node, 4)
        insert(node, 7)
        assert_equal(validate_bst(node), True)

        root = Node(5)
        left = Node(5)
        right = Node(8)
        invalid = Node(20)
        root.left = left
        root.right = right
        root.left.right = invalid
        assert_equal(validate_bst(root), False)

        print('Success: test_bst_validate')


def main():
    test = TestBstValidate()
    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