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.
My code:
# 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==None:
return True
label=self.check_tree(root,None,None)
return bool(label)
def check_tree(self,root,value1,value2):
if root==None:
return True
print('root value %d'%(root.val))
left=root.left
label1=True
if left!=None:
print('left value %d'%left.val)
if left.val>=root.val:
return False
if value1 is not None and left.val<=value1:
return False
value22=root.val
label1=self.check_tree(left,value1,value22)
right=root.right
label2=True
if right!=None:
print('right value %d'%right.val)
if right.val<=root.val:
return False
print('1st satisfied')
print(value2)
if value2 is not None and right.val>=value2:
return False
value11=root.val
label2=self.check_tree(right,value11,value2)
print(label1 and label2)
print('finishing the loop')
return label1 and label2
Solution: https://leetcode.com/problems/validate-binary-search-tree/