LeetCode: Validate Binary Search Tree

Posted on January 9, 2018July 26, 2020 by braindenny

Basic tree datastructure

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

## https://code.dennyzhang.com/validate-binary-search-tree
## Basic Ideas: in-order
##
## Complexity: Time O(n), Space O(1)
# 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: TreeNode) -> bool:
        prev = -sys.maxsize
        def dfs(root):
            if not root: return True
            nonlocal prev
            if not dfs(root.left):
                return False
            if prev != -sys.maxsize and prev>=root.val:
                return False
            prev = root.val
            return dfs(root.right)
        return dfs(root)

Post Views: 1