Recursion, Trees
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:
This tree isn’t valid, as the left-hand 3 is wrong (it’s less than 2):
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:
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
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.
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.