0098.Validate Binary Search Tree

Link: 98. Validate Binary Search Tree
Track: Amazon Tag

Question

Restate the problem

• Given the root of binary tree
• determine if it is a valid binary search tree

---

Method 1 - DFS (Top - down)
Method 2

Method 1 - DFS

if not (low_bound <= node <= high_bound) , return False

Approach

• Use DFS and pass down two bounds(low, high)
  • Base case: if node is None, return True
  • If it violate the BST rule, return False
  • Recurse:
    • Left subtree must in (low, node.val)
    • Right subtree must in (node.val, high)

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Edge Case

• If no tree, return True

Code

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(node, low, high):
            if not node:
                return True
 
            if node.val <= low or node.val >= high:
                return False
 
            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
        
        return dfs(root, float('-inf'), float('inf'))

Sample:

5 low: -inf high: inf
    - left: 1  low: -inf high: 5
        - true, true
    - right: 4 low: 5 high: inf ---> return False
        - left: 3 low: 5 high: 4
        - right: 6 low: 4 high: inf

---

History

• Jan-08-2026 Peeked