LeetCode 98 - Validate Binary Search Tree

LeetCode Problem 98

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to determine whether a given binary tree satisfies the rules of a Binary Search Tree, commonly abbreviated as BST.

A binary tree consists of nodes where each node contains a value and pointers to a left child and a right child. In a BST, every node must follow these rules:

• Every value in the left subtree must be strictly smaller than the current node’s value.
• Every value in the right subtree must be strictly greater than the current node’s value.
• Both subtrees themselves must also satisfy the BST property recursively.

The important detail is that the constraint applies to the entire subtree, not just the immediate children.

For example, consider this tree:

    5
   / \
  1   4
     / \
    3   6

At first glance, node 4 is smaller than 5, which already violates the BST rule because it is located in the right subtree of 5. Even though 3 < 4 and 6 > 4, the tree is still invalid because all nodes in the right subtree of 5 must be greater than 5.

The input is the root node of a binary tree. The output is a boolean:

• True if the tree is a valid BST
• False otherwise

The constraints tell us the tree can contain up to 10^4 nodes. This means we should aim for an efficient traversal solution, ideally linear time. The node values can range from -2^31 to 2^31 - 1, which means we must be careful when handling boundary values and should avoid relying on fixed integer sentinels that may overflow.

Several edge cases are important:

• A single-node tree is always a valid BST.
• Duplicate values are not allowed because the rules require strictly smaller and strictly greater values.
• A tree may appear locally valid while being globally invalid.
• Very deep trees may create large recursion depth.
• Negative values and extremely large values must still work correctly.

A naive implementation often fails because it only compares each node with its direct children instead of validating the entire allowable range for every subtree.

Approaches

Brute Force Approach

A straightforward approach is to validate each node independently by checking:

• Every value in the left subtree is smaller than the node
• Every value in the right subtree is greater than the node

To do this, for every node we can:

1. Find the maximum value in the left subtree
2. Find the minimum value in the right subtree
3. Verify the BST condition
4. Recursively repeat for children

This works because it explicitly checks the BST definition at every node.

However, this approach is inefficient because subtree values are repeatedly traversed. For example, finding subtree minima and maxima for every node causes many repeated computations.

In the worst case, each node may scan almost the entire tree again, leading to quadratic complexity.

Optimal Approach

The key insight is that every node in a BST must lie within a valid numeric range determined by its ancestors.

For example:

• The left child of 10 must be less than 10
• The right child of 10 must be greater than 10
• If we move to the right child 15, then every node under it must still remain greater than 10

Instead of checking subtrees repeatedly, we propagate valid lower and upper bounds during traversal.

When visiting a node:

• Its value must be strictly greater than the lower bound
• Its value must be strictly smaller than the upper bound

As we recurse:

• The left subtree receives an updated upper bound
• The right subtree receives an updated lower bound

This guarantees that every node satisfies all ancestor constraints simultaneously.

Since each node is visited exactly once, the solution runs in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly scans subtrees for min/max values
Optimal	O(n)	O(h)	Uses recursive bounds propagation during DFS traversal

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

1. Start a depth-first traversal from the root node.

Initially, the root has no restrictions, so its valid range is (-∞, +∞). 2. At each node, verify that its value lies strictly within the allowed range.

If the node value is less than or equal to the lower bound, the BST property is violated.

If the node value is greater than or equal to the upper bound, the BST property is violated. 3. Recursively validate the left subtree.

Every node in the left subtree must be smaller than the current node, so:

• The upper bound becomes the current node’s value
• The lower bound remains unchanged

4. Recursively validate the right subtree.

Every node in the right subtree must be greater than the current node, so:

• The lower bound becomes the current node’s value
• The upper bound remains unchanged

5. If a null node is reached, return True.

An empty subtree is always a valid BST. 6. Combine the results.

A node is valid only if:

• Its value satisfies the bounds
• Its left subtree is valid
• Its right subtree is valid

Why it works

The algorithm maintains an invariant:

Every recursive call receives the exact valid range that all nodes in that subtree must satisfy.

Because ancestor constraints are propagated downward, no node can violate a BST rule without failing the range check. Every node is checked exactly once against all relevant constraints, which guarantees correctness.

Python Solution

# 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

from typing import Optional

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

        def validate(
            node: Optional[TreeNode],
            lower: float,
            upper: float
        ) -> bool:

            if not node:
                return True

            if node.val <= lower or node.val >= upper:
                return False

            left_valid = validate(node.left, lower, node.val)
            right_valid = validate(node.right, node.val, upper)

            return left_valid and right_valid

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

The implementation defines a helper function named validate that performs recursive DFS traversal while carrying valid numeric bounds.

The base case handles null nodes. Since an empty subtree cannot violate BST rules, the function returns True.

For every real node, the algorithm checks whether the node value falls strictly between the lower and upper bounds. If not, the function immediately returns False.

The recursive calls update the bounds appropriately:

• The left subtree receives the current node value as its new upper bound.
• The right subtree receives the current node value as its new lower bound.

Finally, both subtree results are combined with logical AND. The entire tree is valid only if every subtree satisfies BST rules.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "math"

func isValidBST(root *TreeNode) bool {

    var validate func(node *TreeNode, lower, upper int64) bool

    validate = func(node *TreeNode, lower, upper int64) bool {

        if node == nil {
            return true
        }

        value := int64(node.Val)

        if value <= lower || value >= upper {
            return false
        }

        leftValid := validate(node.Left, lower, value)
        rightValid := validate(node.Right, value, upper)

        return leftValid && rightValid
    }

    return validate(root, math.MinInt64, math.MaxInt64)
}

The Go implementation follows the same recursive strategy as the Python version.

One important difference is integer handling. Since node values may reach the limits of 32-bit integers, the solution uses int64 bounds with math.MinInt64 and math.MaxInt64 to avoid overflow issues.

Go uses nil instead of Python’s None for empty nodes. Otherwise, the recursive logic remains identical.

Worked Examples

Example 1

Input: [2,1,3]

    2
   / \
  1   3

Initial call:

validate(2, -inf, +inf)

Current Node	Lower Bound	Upper Bound	Valid?
2	-inf	+inf	Yes

Recursive calls:

Left subtree:

validate(1, -inf, 2)

Current Node	Lower Bound	Upper Bound	Valid?
1	-inf	2	Yes

Both children are null, so they return True.

Right subtree:

validate(3, 2, +inf)

Current Node	Lower Bound	Upper Bound	Valid?
3	2	+inf	Yes

Both children are null, so they return True.

Final result:

True

Example 2

Input: [5,1,4,null,null,3,6]

      5
     / \
    1   4
       / \
      3   6

Initial call:

validate(5, -inf, +inf)

Current Node	Lower Bound	Upper Bound	Valid?
5	-inf	+inf	Yes

Left subtree:

validate(1, -inf, 5)

Current Node	Lower Bound	Upper Bound	Valid?
1	-inf	5	Yes

Right subtree:

validate(4, 5, +inf)

Current Node	Lower Bound	Upper Bound	Valid?
4	5	+inf	No

Node 4 violates the lower bound because it is inside the right subtree of 5 but is smaller than 5.

The algorithm immediately returns:

False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack depends on tree height

The DFS traversal processes each node one time and performs only constant-time work per node.

The recursive stack depth depends on tree height:

• Balanced tree: O(log n)
• Completely skewed tree: O(n)

No additional data structures proportional to the number of nodes are used.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3)

assert solution.isValidBST(root1) is True  # valid BST

# Example 2
root2 = TreeNode(5)
root2.left = TreeNode(1)
root2.right = TreeNode(4)
root2.right.left = TreeNode(3)
root2.right.right = TreeNode(6)

assert solution.isValidBST(root2) is False  # right subtree violation

# Single node tree
root3 = TreeNode(1)

assert solution.isValidBST(root3) is True  # single node always valid

# Duplicate values
root4 = TreeNode(2)
root4.left = TreeNode(2)

assert solution.isValidBST(root4) is False  # duplicates not allowed

# Deep left subtree violation
root5 = TreeNode(10)
root5.left = TreeNode(5)
root5.right = TreeNode(15)
root5.right.left = TreeNode(6)
root5.right.right = TreeNode(20)

assert solution.isValidBST(root5) is False  # 6 violates root constraint

# Valid complex BST
root6 = TreeNode(8)
root6.left = TreeNode(3)
root6.right = TreeNode(10)
root6.left.left = TreeNode(1)
root6.left.right = TreeNode(6)
root6.left.right.left = TreeNode(4)
root6.left.right.right = TreeNode(7)
root6.right.right = TreeNode(14)

assert solution.isValidBST(root6) is True  # larger valid BST

# Negative values
root7 = TreeNode(0)
root7.left = TreeNode(-1)
root7.right = TreeNode(1)

assert solution.isValidBST(root7) is True  # handles negatives correctly

# Right child smaller than parent
root8 = TreeNode(5)
root8.right = TreeNode(4)

assert solution.isValidBST(root8) is False  # immediate violation

# Left child greater than parent
root9 = TreeNode(5)
root9.left = TreeNode(6)

assert solution.isValidBST(root9) is False  # immediate violation

Test Summary

Test	Why
[2,1,3]	Basic valid BST
[5,1,4,null,null,3,6]	Detects subtree constraint violation
Single node	Smallest valid tree
Duplicate values	Ensures strict inequality
Deep subtree violation	Verifies ancestor bounds propagation
Large valid BST	Confirms recursive correctness
Negative values	Tests signed integer handling
Invalid right child	Detects direct BST violation
Invalid left child	Detects opposite direct violation

Edge Cases

Duplicate Values

BST rules require strict inequality. Many incorrect implementations allow duplicates by using <= or >= incorrectly.

For example:

    2
   /
  2

This is not a valid BST because the left child must be strictly smaller than the parent.

The implementation handles this correctly with:

if node.val <= lower or node.val >= upper:

This rejects duplicate values immediately.

Deep Subtree Violations

A common mistake is checking only immediate children.

Consider:

      10
     /  \
    5    15
        /
       6

Node 6 is smaller than 10, so it cannot appear in the right subtree of 10.

Naive parent-child comparisons miss this issue because 6 < 15 appears valid locally.

The range propagation technique correctly passes 10 as the lower bound throughout the entire right subtree, so 6 fails validation.

Extreme Integer Values

The constraints allow values near the limits of 32-bit integers.

Using fixed integer sentinels like -2^31 and 2^31 - 1 as boundaries may create overflow or comparison issues.

The Python solution avoids this by using positive and negative infinity.

The Go solution avoids overflow by using int64 bounds with math.MinInt64 and math.MaxInt64.

This guarantees safe comparisons for all valid inputs.