Validate Binary Search Trees

Problem

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

Assume a 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.

For example:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but 
its right child's value is 4.

Solution

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        self.val = True
        self.helper(root, self.val)
        return self.val
    def helper(self, root, val):
        if root is None:
            return 
        self.helper(root.left, val)
        if self.prev != None:
            if self.prev.val >= root.val:
                self.val = False
                return
        self.prev = root
        self.helper(root.right, val)
            
#Time: O(log n) which is the height
#Space: O(log n) as well