Determine if BST is valid: failing some test cases

Question

I am trying to find a solution for LeetCode problem 98. Validate Binary Search Tree:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Following is the code that is already provided:

class TreeNode(object):
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

class Solution(object):
    def isValidBST(self, root):
        # your code

Following is my implementation:

class Solution(object):
    def isValidBST(self, root):
        if not root:
            return []
        if self.isValidBST(root.left)< [root.val] < self.isValidBST(root.right):
            return True
        else:
            return False

Problem

The code passes a few test cases (like root = [5,1,4,null,null,3,6]), but also fails a few. For example, it fails the following test:

• Input: root = [2,1,3], which represents this tree:

      2
     / \
    1   3
  

• Expected output: True

My code returns False.

What is my mistake?

Answer 1

The main problem with this implementation is that isValidBST is supposed to return a boolean, so the following pieces of code don't make sense:

• return []: that should be return True
• self.isValidBST(root.left)< [root.val]: this would be comparing a boolean with a list, which is not supported (nor does it have a meaning). Even if you expected the function to return a list here, that list would be empty (as you only return [] as a list -- see previous point).

A way to make it work is to pass extra (optional) arguments to isValidBST that provide a "window" (range) for the values of the given tree: all its nodes should have values within that window or it is not a BST. Initially that window can be set with default values to -Infinity to Infinity.

Here is a spoiler in case you cannot make it work:

class Solution(object): def isValidBST(self, root, low=float('-inf'), high=float('inf')): return (not root or low < root.val < high and self.isValidBST(root.left, low, root.val) and self.isValidBST(root.right, root.val, high))

Alternatively you could make a helper function that does not return a boolean, but returns the window (range) that a given subtree actually spans (so its minimum and maximum values). If either span retrieved from the two subtrees violates the current root node's value, it is not a BST. But it is important to see that this function must be a different function from the main function, since the main function must return a boolean.

Yet another alternative is to perform an inorder traversal. Each visited value must be greater than the previously visited value.