Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bug in bst_validate solution #253

Open
maxliu opened this issue Dec 16, 2018 · 0 comments
Open

Bug in bst_validate solution #253

maxliu opened this issue Dec 16, 2018 · 0 comments

Comments

@maxliu
Copy link

maxliu commented Dec 16, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants