Start learning free

LESSON 407 OF 535 · BINARY TREES

Validate Binary Search Tree in C++: Passing Bounds Down in O(n)

Practice O(n) Read the full explanation

Given the root of a binary tree, return true if it is a valid binary search tree (BST), and false otherwise.

A binary tree is a valid BST when, for every node:

every value in its left subtree is strictly smaller than the node's value,
every value in its right subtree is strictly larger than the node's value.

The rule is about the whole subtree, not only the children: a node's value must also fit every node above it.

The trees below are written in level order (top to bottom, left to right), with NULL for a missing child.

Example 1:

     2
    / \
   1   3

Input: root = [2,1,3]
Output: true
Explanation: 1 is smaller than 2 and 3 is larger.

Example 2:

     5
    / \
   1   4
      / \
     3   6

Input: root = [5,1,4,NULL,NULL,3,6]
Output: false
Explanation: The right child of the root 5 is 4, which is smaller than 5.

Example 3:

     5
    / \
   4   6
      / \
     3   7

Input: root = [5,4,6,NULL,NULL,3,7]
Output: false
Explanation: Every node is in order with its own children: 4 < 5 < 6 and 3 < 6 < 7. But 3 is in the right subtree of 5, where every value must be larger than 5. Comparing each node only with its children misses this: each node must lie in the range that all of its ancestors set.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
Each node value is between -2³¹ and 2³¹ - 1.
The tree is at most 800 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, visiting each node once.

Node values can be the smallest and the largest 32-bit integers, so a bound that means "no limit yet" can't be one of those values.

STEP 1 OF 5

Guided

Ctrl + Enter to check

C++ · BINARY TREES

Validate Binary Search Tree in C++, explained

Problem overview

The method isValidBST receives the root of a binary tree and returns true if it is a valid binary search tree. For every node, all values in its left subtree must be strictly smaller than the node's value, and all values in its right subtree must be strictly larger. The rule covers the whole subtree, not only the children. The lesson provides TreeNode, with an int val and two TreeNode * fields, left and right.

The tree with root 2 and children 1 and 3 is valid. The tree with root 5, left child 1 and right child 4 (whose children are 3 and 6) is not: 4 is in the right subtree of 5 but is smaller than 5. The third example is the instructive one: root 5 with children 4 and 6, and 6 has children 3 and 7. Every node is in order with its own children, since 4 < 5 < 6 and 3 < 6 < 7, but the 3 sits in the right subtree of 5, where every value must be larger than 5. The answer is false.

Approach: every node lives inside a range

Comparing each node only with its children is not enough, as the third example shows. A node's value has to respect every ancestor. Going down from the root, each ancestor narrows the allowed range:

Going into the left child of a node with value v means every value there must be below v, so the upper bound becomes v.
Going into the right child means every value there must be above v, so the lower bound becomes v.

The other bound is inherited unchanged. A node is valid when its value lies strictly between the current lower and upper bounds, and both of its subtrees are valid with their own tightened ranges. The root starts with no limits at all.

In the third example, the 6 is reached with the range (5, no limit), so it fits. Its left child 3 is reached with the range (5, 6), and 3 is not above 5, so the answer is false.

"No limit" needs a value that no node can reach. Node values range over all 32-bit integers, so neither INT_MIN nor INT_MAX can stand for "unbounded": a node holding that very value would be rejected, because the check is strict. The lesson uses the 64-bit type long long for the bounds, with LLONG_MIN and LLONG_MAX as the starting limits. Every int is strictly between them.

Step by step

Call a helper from isValidBST: validate(root, LLONG_MIN, LLONG_MAX), and return its answer. The root has nothing above it, so nothing limits its value yet.
Write validate above isValidBST. It returns a bool and takes a TreeNode* named node and two long long bounds, low and high. It answers whether every value in the subtree under node is larger than low and smaller than high.
Accept an empty subtree: if !node, return true. An empty tree breaks no rule, and this test ends the recursion past the leaves.
Reject a value out of range: if node->val <= low || node->val >= high, return false. The comparison is strict, so a value equal to a bound is rejected too, which makes duplicates invalid.
Check both subtrees with &&: the left one gets the range (low, node->val) and the right one gets (node->val, high).

The solution in C++

class Solution {
public:
    bool validate(TreeNode* node, long long low, long long high) {
        if (!node) {
            return true;
        }
        if (node->val <= low || node->val >= high) {
            return false;
        }
        return validate(node->left, low, node->val) && validate(node->right, node->val, high);
    }

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

C++ details worth a closer look:

Why long long. A tree holding the single value INT_MAX is a valid BST. A version of validate with int bounds and INT_MIN and INT_MAX as the starting limits returns false for it, because INT_MAX >= high. With long long bounds it returns true. LLONG_MIN and LLONG_MAX are -9223372036854775808 and 9223372036854775807.
Mixed comparisons. node->val is an int and low is a long long. C++ converts the int to long long before comparing, so the comparison is exact. Passing node->val as a long long argument converts the same way.
!node. A null pointer is false in a condition, so !node is true exactly when node is nullptr.
Short-circuit &&. If the left subtree is invalid, the right subtree is not examined at all. The answer is already false.
Constants from <climits>. LLONG_MIN and LLONG_MAX are defined there. In a file of your own, add #include <climits> or #include <bits/stdc++.h>.

Complexity

Time: O(n), where n is the number of nodes. Each node is visited once, and each visit does a constant amount of work: two comparisons and two calls.

Space: O(h), where h is the height of the tree, for the recursion stack. A balanced tree has h around log n, and a chain has h equal to n. The constraints keep the depth at 800 levels or less.

Edge cases and common mistakes

Checking only the children. The third example passes a children-only check and is still invalid. Passing the bounds down is what catches it.
Duplicates. The rule is strict, so a node with a left child holding the same value is invalid. Root 2 with left child 2 returns false. Using < and > in the rejection test, instead of <= and >=, would accept it.
Extreme values. A single node with INT_MAX or INT_MIN is valid. So is root INT_MIN with right child INT_MAX. Both work because the starting bounds lie beyond every int.
Using the parent's value only. Replacing both bounds at each step with the parent's value forgets the earlier ancestors, which is the same error as comparing with the children alone.
Dereferencing null. The !node test has to come first. Reading node->val on a null pointer is undefined behaviour.
A single node. A tree of one node is valid, whatever its value.

Testing

Root 2 with children 1 and 3 gives true.
Root 5 with children 1 and 4, where 4 has children 3 and 6, gives false.
Root 5 with children 4 and 6, where 6 has children 3 and 7, gives false.
Root 2 with a left child 2 gives false.
Root 2 with children 2 and 2 gives false.
A single node INT_MAX gives true, and so does a single node INT_MIN.
Root INT_MIN with right child INT_MAX gives true.

Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free