Hackbright Code Challenges

Binary Search Tree Validator

Binary Search Tree Validator

Whiteboard

Harder

Challenge

Medium

Concepts

Recursion, Trees

Download

bst-valid.zip

Solution

Binary Search Tree Validator: Solution


A valid binary search tree follows a specific rule. In our case, the rule is “left child must value must be less-than parent-value” and “right child must be greater-than-parent value”.

This rule is recursive, so everything left of a parent must less than that parent (even grandchildren or deeper) and everything right of a parent must be greater than the parent.

For example, this tree is valid:

digraph valid { rankdir=TB 4 -> {2, 6} 2 -> {1, 3} 6 -> {5, 7} }

This tree isn’t valid, as the left-hand 3 is wrong (it’s less than 2):

digraph invalid { rankdir=TB 4 -> {2, 6} 2 -> {a3, b3} 6 -> {5, 7} a3 [label="3" color="red"] b3 [label="3"] }

This tree is invalid, as the bottom-right 1 is wrong — it is less than its parent, 6, but it’s also less than its grandparent, 4, and therefore should be left of 4:

digraph invalid2 { rankdir=TB 4 -> {2, 6} 2 -> {a1, 3} 6 -> {b1, 7} a1 [label="1"] b1 [label="1" color="red"] }

Your Challenge

Your challenge is to write a method that, given a node in a binary search tree, returns True or False depending on whether the tree rooted at that node is valid.

For example, checking the three trees above:

>>> t = Node(4,
...       Node(2, Node(1), Node(3)),
...       Node(6, Node(5), Node(7))
... )

>>> t.is_valid()
True

>>> t = Node(4,
...       Node(2, Node(3), Node(3)),
...       Node(6, Node(5), Node(7))
... )

>>> t.is_valid()
False

>>> t = Node(4,
...       Node(2, Node(1), Node(3)),
...       Node(6, Node(1), Node(7))
... )

>>> t.is_valid()
False

Starting Code

We’ve provided a Node class for you that takes three values: the data, a reference to the left child, and a reference to the right child.

bstvalid.py
class Node:
    """Binary search tree node."""

    def __init__(self, data, left=None, right=None):
        """Create node, with data and optional left/right."""

        self.left = left
        self.right = right
        self.data = data

    def is_valid(self):
        """Is this tree a valid BST?"""

When you’ve completed the function properly, all tests will pass.