Python solution (linear time, and linear space) using in-order traversal with explanation

  • 1
    # linear time, and linear space complexity
    def isValidBST(self, root):
        def inorder_list(node):
            if not node:
                return []
            return inorder_list(node.left) + [node.val] + inorder_list(node.right)
        inorder_list = inorder_list(root)
        for i in range(len(inorder_list)-1):
            if inorder_list[i] >= inorder_list[i+1]:
                return False
        return True

    Explanation: Essentially create a list via inorder traversal, and then compare each element to its neighbor element. If at any point the left element is greater than, or equal to the right element, that means it is not a legal BST (according to definition in the requirements)

Log in to reply

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