The challenge
Check that every descendant follows strict BST ordering with respect to all its ancestors.
Duplicates are invalid. Empty trees are valid. Values are finite integers.
Example
The second example places 6 in the right subtree of 8: it is below parent 12 but still violates the lower bound 8.
Use the walkthrough below to inspect the input and each state change.
See Validate BST, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Pass an open interval of legal values down each path.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_valid_bst(root):
def valid(node, low, high):
if node is None:
return True
if not low < node.value < high:
return False
return (valid(node.left, low, node.value)
and valid(node.right, node.value, high))
return valid(root, float("-inf"), float("inf"))
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
bool is_valid_bst(Node* root) {
function<bool(Node*, optional<long long>, optional<long long>)> valid =
[&](Node* node, optional<long long> low, optional<long long> high) {
if (!node) return true;
if ((low && node->value <= *low) || (high && node->value >= *high))
return false;
return valid(node->left, low, node->value)
&& valid(node->right, node->value, high);
};
return valid(root, nullopt, nullopt);
}