donnemartin / interactive-coding-challenges

120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
Other
29.44k stars 4.45k forks source link

Bug in bst_validate solution #253

Open maxliu opened 5 years ago

maxliu commented 5 years ago

The solution for bst_validate won't work if the tree has a node with the value of -sys.maxsize.

A suggested tweak would be to use None instead of sys.maxsize and -sys.maxsize.

 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=None, maximum=None):
        if node is None:
            return True

        if not ((minimum is None or node.data>minimum) and (maximum is None 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

I would be happy to prepare a PR if this makes sense to you.