LeetCode 98: Validate Binary Search Tree with DFS Value Bounds

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

This problem asks us to determine whether a binary tree satisfies the rules of a binary search tree, or BST.

The main challenge is that checking only a node and its immediate children is not sufficient. Every node must also respect restrictions created by all of its ancestors. We can preserve those restrictions by performing a depth-first search while passing a valid lower bound and upper bound to each recursive call.

This article explains how to derive that approach, why strict bounds are necessary, and how to implement it safely in C++.

Original Problem and Credit

This article is based on the LeetCode problem “98. Validate Binary Search Tree.”

• Original problem: https://leetcode.com/problems/validate-binary-search-tree/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The task is to determine whether the given binary tree is a valid binary search tree.

A valid BST must satisfy all of the following rules:

• Every value in a node's left subtree must be strictly smaller than the node's value.
• Every value in a node's right subtree must be strictly greater than the node's value.
• Both subtrees must also satisfy the same BST rules.

The important word is strictly. Equal values are not valid in either subtree.

Constraints

• The tree contains between 1 and 10^4 nodes.
• Each node value is between -2^31 and 2^31 - 1.

Real-World Scenario

Consider a hypothetical data platform that stores versioned configuration records in a binary search tree.

Each tree node contains a unique numeric configuration key:

• Smaller keys must be stored somewhere in the left subtree.
• Larger keys must be stored somewhere in the right subtree.
• Duplicate keys are not allowed.

Before the tree is persisted or used for fast lookup, a validation service must confirm that the entire structure follows the ordering contract.

It is not enough to validate only direct parent-child relationships. A record can be smaller than its parent but still violate a restriction established by an earlier ancestor.

For example, suppose a key appears in the right subtree of key 5. Every key in that entire subtree must be greater than 5, even when the key is several levels below the root.

This hypothetical validation workflow is mathematically equivalent to validating the BST in the original problem.

Examples

Example 1: Valid BST

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

The value 1 is smaller than 2, and the value 3 is greater than 2. Both subtrees satisfy the required ordering.

Example 2: Invalid BST

Input: root = [5,1,4,null,null,3,6]
Output: false

The node with value 4 is in the right subtree of 5. Therefore, it must be greater than 5, but 4 < 5.

The local relationship between 4 and its child 3 does not repair the ancestor-level violation.

Mapping to the Original Problem

The scenario changes only the terminology. The tree structure, ordering rules, input, output, and invalid conditions remain unchanged.

Solution Intuition

Why checking only direct children fails

A first attempt may check these conditions at every node:

left child < current node < right child

That test is necessary, but it is not sufficient.

In Example 2, node 4 is a valid local parent for node 3 and node 6 because:

3 < 4 < 6

However, node 4 is inside the right subtree of 5. Every node in that subtree must be greater than 5. Because 4 is not greater than 5, the complete tree is invalid.

This tells us that each recursive call needs more information than the parent value alone.

Carry the valid range

For every node, maintain an open interval:

lower bound < node value < upper bound

The bounds are strict because duplicate values are not allowed.

At the root, there are no practical restrictions, so its valid interval is:

negative infinity < root value < positive infinity

When moving to the left child:

• The lower bound stays the same.
• The current node's value becomes the new upper bound.

When moving to the right child:

• The current node's value becomes the new lower bound.
• The upper bound stays the same.

In other words:

validate left subtree with (lower, current value)
validate right subtree with (current value, upper)

Because the bounds are passed through every recursive level, each node automatically respects every relevant ancestor.

Why use long long bounds?

A node value may equal INT_MIN or INT_MAX because the allowed values cover the full 32-bit signed integer range.

Using those same values as exclusive initial bounds would incorrectly reject a valid node whose value is exactly at one of those limits.

Instead, we use LLONG_MIN and LLONG_MAX, which extend beyond the possible int node values.

Algorithm

1. Start a depth-first search at the root with LLONG_MIN as the lower bound and LLONG_MAX as the upper bound.
2. If the current node is nullptr, return true. An empty subtree cannot violate the BST rules.
3. Check whether the node value lies strictly between its bounds.
4. If node->val <= lower or node->val >= upper, return false immediately.
5. Recursively validate the left subtree with the same lower bound and the current value as its upper bound.
6. Recursively validate the right subtree with the current value as its lower bound and the same upper bound.
7. Return true only when both subtrees are valid.

Why the Algorithm Works

The main invariant is:

Every recursive call receives exactly the range of values allowed at that node by all of its ancestors.

At the root, the initial range allows every possible int value.

For a left child, setting the current node's value as the upper bound ensures that the child and all of its descendants remain strictly smaller than the current node. Any older lower-bound restriction is preserved.

For a right child, setting the current node's value as the lower bound ensures that the child and all of its descendants remain strictly greater than the current node. Any older upper-bound restriction is preserved.

If a node falls outside its allowed range, it violates at least one ancestor's ordering rule, so the tree cannot be a valid BST.

If every node lies inside its inherited range, then every left subtree contains only smaller values, every right subtree contains only larger values, and the property holds recursively throughout the tree. Therefore, the tree is a valid BST.

Complexity Analysis

Let n be the number of nodes in the tree, and let h be the tree's height.

Time Complexity

O(n)

The depth-first search visits each node exactly once. Each visit performs a constant amount of work: two comparisons and the creation of recursive calls.

Therefore, the total time complexity is O(n).

Space Complexity

O(h)

The algorithm does not create an additional data structure that grows with the number of nodes. However, the recursive calls use the program's call stack.

• In a balanced tree, h = O(log n).
• In a completely skewed tree, h = O(n).

Therefore, the auxiliary space complexity is O(h), which is O(n) in the worst case.

C++ Solution: DFS with Valid Value Bounds

#include <climits>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode* left;
 *     TreeNode* right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode* left, TreeNode* right)
 *         : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    bool validate(
        TreeNode* node,
        long long lowerBound,
        long long upperBound
    ) {
        if (node == nullptr) {
            return true;
        }

        if (node->val <= lowerBound || node->val >= upperBound) {
            return false;
        }

        return validate(node->left, lowerBound, node->val) &&
               validate(node->right, node->val, upperBound);
    }

public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LLONG_MIN, LLONG_MAX);
    }
};

Walkthrough

Consider the invalid tree from Example 2:

root = [5,1,4,null,null,3,6]

The traversal begins with node 5:

Allowed range: (-infinity, +infinity)

5 is inside the range, so the algorithm continues.

Visit the left subtree

Node 1 receives:

Allowed range: (-infinity, 5)

Because 1 < 5, this node is valid. Its missing children also return true.

Visit the right subtree

Node 4 receives:

Allowed range: (5, +infinity)

The test is:

4 > 5

This condition is false. Node 4 violates the lower bound inherited from root 5, so the algorithm immediately returns false.

Notice that the algorithm does not need to inspect nodes 3 and 6. Once a definite violation is found, early termination is correct.

Common Mistakes

Checking only immediate children

A node may be correctly ordered relative to its parent but incorrectly ordered relative to an earlier ancestor. Carry the complete valid range instead.

Allowing equality

The BST definition in this problem requires strict ordering. Use:

node->val <= lowerBound || node->val >= upperBound

Using only < and > in the invalidity check would allow duplicate values.

Using INT_MIN and INT_MAX as exclusive bounds

A valid node may contain either limit. Use a wider type such as long long with LLONG_MIN and LLONG_MAX.

Passing incorrect bounds to children

The left subtree keeps the existing lower bound and receives the current value as its new upper bound. The right subtree receives the current value as its new lower bound and keeps the existing upper bound.

Forgetting the empty-subtree base case

A nullptr subtree is valid and should return true.

Key Takeaways

• A BST is governed by ancestor-level ordering rules, not only parent-child comparisons.
• Passing lower and upper bounds preserves all relevant ancestor restrictions.
• The bounds must be strict because duplicates are invalid.
• Wider integer bounds prevent errors at INT_MIN and INT_MAX.
• DFS validates the complete tree in O(n) time with O(h) recursive stack space.