98. Validate Binary Search Tree

[#binary-tree, #dfs]

## description

## 98. Validate Binary Search Tree

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

A valid BST is defined as follows:

–
The left subtree of a node contains only nodes with keys strictly less than the node's key.
–
The right subtree of a node contains only nodes with keys strictly greater than the node's key.
–
Both the left and right subtrees must also be binary search trees.

Example 1:

plain text

Input: root = [2,1,3]
Output: true

Example 2:

plain text

Input: root = [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.

–
The number of nodes in the tree is in the range [1, 104].
–
-231 <= Node.val <= 231 - 1

Constraints:

## notes

### Intuition

A node is valid when it is in the range of values that is decided by it's ancestors. When going deeper, the range is updated. For the root, the range starts with (-inf, inf), going left upper bound is updated, going right lower bound is updated.

### Implementation

This problem can be solved with DFS. We start by defining our recursive function that takes in a node and the left and right bounds. If the node is None, that is valid node, we can return True. Otherwise, we check if the value is NOT in the range and early return false. Finally, we call the function recursively on left AND right with the updates bounds. For the left node, the lower bound stays the same but the upper bound is updated to the current value. For the right node, the lower bound is updated to the current value and the upper bound stays the same.

Finally, we call the recursive function on the root with -inf, inf as our bounds (using sys.maxsize or float("inf")/float("-inf')).

–
Time: O(n), we visit each node, at most, once.
–
Space: O(n), recursive call stack

### Complexity

## solution

python

import sys
from typing import Optional
from lcutils import TreeNode

# 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: Optional[TreeNode]) -> bool:
        def valid(node: Optional[TreeNode], left: int, right: int) -> bool:
            if not node:
                return True
            if not (left < node.val < right):
                return False
            return valid(node.left, left, node.val) and valid(node.right, node.val, right)

        max_int = sys.maxsize - 1
        return valid(root, -max_int, max_int)


if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()
    print("hello world")

--EOF--