Clean Python Solution

  • 26

    Use recursion. Pass down two parameters: lessThan (which means that all nodes in the the current subtree must be smaller than this value) and largerThan (all must be larger than it). Compare root of the current subtree with these two values. Then, recursively check the left and right subtree of the current one. Take care of the values passed down.

    class Solution(object):
        def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')):
            if not root:
                return True
            if root.val <= largerThan or root.val >= lessThan:
                return False
            return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and \
                   self.isValidBST(root.right, lessThan, max(root.val, largerThan))

  • 0

    So freaking brilliant.
    Short and elegant!

  • 0

    wouldn't min(lessThan, root.val) and max(root.val, largerThan) return always root.val?

  • 0

    Yes they will...

  • 20

    might be more intuitive:

    def isValidBST(self, root, floor=float('-inf'), ceiling=float('inf')):
        if not root: 
            return True
        if root.val <= floor or root.val >= ceiling:
            return False
        # in the left branch, root is the new ceiling; contrarily root is the new floor in right branch
        return self.isValidBST(root.left, floor, root.val) and self.isValidBST(root.right, root.val, ceiling)

  • 4

    Might be 1-linear:

        def isValidBST(self, root, left = float('-inf'), right = float('inf'),):
            return not root or left < root.val < right and \
                    self.isValidBST(root.left, left, root.val) and \
                    self.isValidBST(root.right, root.val, right)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.