Validate Binary Search Tree
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: 2 / \ 1 3 Binary tree [2,1,3], return true. Example 2: 1 / \ 2 3 Binary tree [1,2,3], return false.
URL: https://leetcode.com/problems/validate-binary-search-tree/
# 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 __init__(self):
self.lastPrinted = -sys.maxsize-1
# @param {TreeNode} root
# @return {boolean}
def isValidBST(self, root):
if root == None:
return True
if self.isValidBST(root.left) == False:
return False
data = root.val
if data <= self.lastPrinted:
return False
self.lastPrinted = data
if self.isValidBST(root.right) == False:
return False
return True