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.


Example 1:


Input:
    2
   / \
  1   3
Output: true


Example 2:


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

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution(object):
         def validBST(self, root, min, max):
             if root == None:
                 return True
             if root.val <= min or root.val >= max:
                 return False
             return self.validBST(root.left, min, root.val) and self.validBST(root.right, root.val, max)
         def isValidBST(self, root):
             return self.validBST(root, -21474836480, 21474836470)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 import sys
 class Solution:
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         if not root or (not root.left and not root.right):
             return True
         return self.isBst(root, [], [])
     def isBst(self, root, min_nums, max_nums):
         # if root:
         #     print("root:", root.val)
         # else:
         #     print("root:", root)
         # print("min_nums", min_nums)
         # print("max_nums", max_nums)
         if not root:
             return True
         min_value = min(min_nums) if min_nums else sys.maxsize
         max_value = max(max_nums) if max_nums else -sys.maxsize-1
         left = self.isBst(root.left, min_nums+[root.val], max_nums)
         right = self.isBst(root.right, min_nums, max_nums+[root.val])
         if root.val < min_value and root.val > max_value and left and right:
             return True
         else:
             return False
             
             

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         if root is None:
             return True
         self.output_list = []
         self.recurse(root)
         print(self.output_list)
         for i in range(len(self.output_list) - 1):
             if self.output_list[i+1] <= self.output_list[i]:
                 return False
         return True
         
     def recurse(self, root):
         """
         :type root: TreeNode
         """
 
         if root.left is not None and root.right is not None:
             self.recurse(root.left)
             self.output_list.append(root.val)
             self.recurse(root.right)
         elif root.left is not None:
             self.recurse(root.left)
             self.output_list.append(root.val)
         elif root.right is not None:
             self.output_list.append(root.val)
             self.recurse(root.right)
         else:
             self.output_list.append(root.val)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         # Time: O(|V| + |E|) = O(n)
         # Space: O(log(n))
         def isValid(node, lo, hi):
             if lo != None:
                 if node.val <= lo:
                     return False
             if hi != None:
                 if node.val >= hi:
                     return False
             if node.left != None:
                 if not isValid(node.left, lo, node.val):
                     return False
             if node.right != None:
                 if not isValid(node.right, node.val, hi):
                     return False
             return True
         
         if root == None: return True
         return isValid(root, None, None)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 import sys
 
 class Solution:
     def isValidBST(self, root):
         return isBSTUtil(root, -sys.maxsize, sys.maxsize)
     
 
 def isBSTUtil(root, min, max):
     if root == None:
         return True
     
     if root.val <= min or root.val >= max:
         return False
     
     return isBSTUtil(root.left, min, root.val) and isBSTUtil(root.right, root.val, max)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def isValidBST(self, node):
         """
         :type root: TreeNode
         :rtype: bool
         """
         def valid(somenode, ceiling, floor):
             if somenode is None:
                 return True
             if somenode.val >= ceiling or somenode.val <= floor:
                 return False
             
             
             return valid(somenode.left, somenode.val, floor) and valid(somenode.right, ceiling, somenode.val)
         
         return valid(node, sys.maxsize, -sys.maxsize)
             
             
          
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def traverse(self, root, hold):
         if root.left:
             self.traverse(root.left, hold)
         hold.append(root.val)
         if root.right:
             self.traverse(root.right, hold)
         
     
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         hold = []
         if not root:
             return True
         self.traverse(root, hold)
         size_tree = len(hold)
         for ele in range(size_tree-1):
             if not hold[ele] < hold[ele+1]:
                 return False
         return True
             

class Solution:
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         if not root:
             return True
 
         return self.dfs(root)[2]
         
     def dfs(self, node):
         """return [min, max, is_BST]"""
         if node is None:
             return [None, None, True]
         
         L = self.dfs(node.left)
         R = self.dfs(node.right)
         if not L[2] or not R[2] \
         or (L[1] is not None and L[1] >= node.val) \
         or (R[0] is not None and R[0] <= node.val):
             return [None, None, False]
         
         if L[0] is not None:
             min = L[0]
         else:
             min = node.val
         if R[1] is not None:
             max = R[1]
         else:
             max = node.val
 
         return [min, max, True]

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     sol = []
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         self.sol = []
         if root is None:
             return True 
         self.traverseBST(root)
         print(self.sol)
         for i in range(1,len(self.sol)):
             if self.sol[i] <= self.sol[i-1]:
                 return False
         return True
     
     # def isValid(self,root):
     #     if root.left and root.right:
     #         if root.left.val< root.val and root.right.val>root.val:
     #             return True
     #     elif root.left:
     #         if root.left.val< root.val:
     #             return True
     #     elif root.right:
     #         if root.right.val>root.val:
     #             return True
     #     else:
     #         return True
     #     return False
 
     
     def traverseBST(self, root):
         if root.left:
             self.traverseBST(root.left)
         print(root.val)
         self.sol.append(root.val)
         # if not self.isValid(root):
         #     return False
         if root.right:
             self.traverseBST(root.right)
         return True
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:   
     
     def valid(self, me, parents_lt, parents_gt):
         if me is None:
             return True
         
         #print(me.val)
         #print(me.left.val) if me.left is not None else print("left: None")
         #print(me.right.val) if me.right is not None else print("right: None")
         #print(parents_lt)
         #print(parents_gt)
         #print('---')
         for p in parents_lt:
             if p.val >= me.val:
                 print('a')
                 return False
         
         for p in parents_gt:
             if p.val <= me.val:
                 print('b')
                 return False
         
         if me.left is not None:
             if me.left.val >= me.val:
                 print('c')
                 return False
             
         if me.right is not None:
             if me.right.val <= me.val:
                 print('d')
                 return False
         gt2 = parents_gt + [me]
         lt2 = parents_lt + [me]
         return self.valid(me.left, parents_lt, gt2) and self.valid(me.right, lt2, parents_gt)
         
     
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         if root is None:
             return True        
         
         return self.valid(root, list(), list())

class Solution(object):
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         res=[]
         return self.inorder(root,res)
 
     def inorder(self,root,res):
         if not root:
             return True
         if self.inorder(root.left,res) == False:
             return False
         if len(res)!=0:
             last = res.pop()
             if last>= root.val:
                 return False
             res.append(last)
         res.append(root.val)
         if self.inorder(root.right,res) == False:
             return False
         return True
 
       
    
 
 
 
 
 


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     
     def inOrderTravel(self,root):
         res = []
         if root == None:
             return []
         
         res += self.inOrderTravel(root.left)
         res.append(root.val)
         res += self.inOrderTravel(root.right)
         
         return res
     
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         res  = self.inOrderTravel(root)
         for i in range(1, len(res)):
             if res[i] <= res[i-1]:
                 return False
         
         return True
         
         
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         stack = []
         pre = None
         while stack or root:
             while root:
                 stack.append(root)
                 root = root.left
             root = stack.pop()
             if pre and root.val <= pre.val: return False
             pre = root
             root = root.right
         return True