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).

Challenge Notebook

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

Constraints
Test Cases
Algorithm
Code
Unit Test
Solution Notebook

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
  / \   /
 4   9 7

Algorithm

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.

Code



In [ ]:

    
%run ../bst/bst.py
%load ../bst/bst.py



In [ ]:

    
def validate_bst(node):
    # TODO: Implement me
    pass

Unit Test

The following unit test is expected to fail until you solve the challenge.



In [ ]:

    
# %load 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()

Solution Notebook

Review the Solution Notebook for a discussion on algorithms and code solutions.