Skip to main content

🟨 Validate Binary Search Tree (#98)

🔗 Problem Link​

📋 Problem Statement​

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 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.

💡 Examples​

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.

🔑 Key Insights & Approach​

Core Observation: Each node must be within a valid range (min, max). Pass range bounds down recursively.

Why Range-Based Validation?

  • O(n) time, O(h) space
  • Handles all subtrees correctly
  • Catches violations like [5,1,4,null,null,3,6]

Approaches:

  1. Recursive with range bounds: O(n) time, O(h) space - optimal
  2. Inorder traversal check: O(n) time, O(n) space

Pattern: "BST Validation" with range bounds.

🐍 Solution: Python​

Approach 1: Recursive with Bounds​

Time Complexity: O(n) | Space Complexity: O(h)

from typing import Optional

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 validate(node, min_val, max_val):
            if not node:
                return True

            # Check current node's value
            if node.val <= min_val or node.val >= max_val:
                return False

            # Validate left and right subtrees with updated bounds
            return (validate(node.left, min_val, node.val) and
                    validate(node.right, node.val, max_val))

        return validate(root, float('-inf'), float('inf'))

Approach 2: Inorder Traversal​

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

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        inorder = []

        def traverse(node):
            if not node:
                return
            traverse(node.left)
            inorder.append(node.val)
            traverse(node.right)

        traverse(root)

        # Check if inorder is strictly increasing
        for i in range(1, len(inorder)):
            if inorder[i] <= inorder[i-1]:
                return False

        return True

🔵 Solution: Golang​

Approach: Recursive with Bounds​

Time Complexity: O(n) | Space Complexity: O(h)

import "math"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
    return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, minVal, maxVal int) bool {
    if node == nil {
        return true
    }

    if node.Val <= minVal || node.Val >= maxVal {
        return false
    }

    return validate(node.Left, minVal, node.Val) &&
           validate(node.Right, node.Val, maxVal)
}

📚 References​