LC 98 - Validate Binary Search Tree

Question

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:

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

Example 2:

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.

Constraints:

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

Links

Question here and solution here

Solution

concept

A naive solution where we just check curr.left.val < curr.val < curr.right.val will not work for case like

    5
   / \
  1   8
     / \
    4   9

due to 4 should satisfy 5<4<8 but it is not. Therefore the way to solve this question is to maintain a range (low, high) such that low < curr.val < high. When we go to the left subtree, we update the high boundary, when we go to the right subtree, we update the low boundary

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: Optional[TreeNode]) -> bool:
        
        def dfs(curr, low, high):
            if not curr:
                return True

            if not (low < curr.val < high):
                return False
    
            left_check = dfs(curr.left, low, curr.val)
            right_check = dfs(curr.right, curr.val, high)

            return left_check and right_check

        return dfs(root, float("-inf"), float("inf"))

Complexity

time: $O(n)$
space: $O(1)$