Validate Binary Search Tree

Medium
1903.

Validate Binary Search Tree

Validate Binary Search Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Given the root of a binary tree, decide whether it is a valid binary search tree:

  • every value in a node's left subtree is strictly smaller than the node's value;
  • every value in a node's right subtree is strictly larger than the node's value;
  • both subtrees are themselves binary search trees.

Return true if it is, false otherwise. Equal values anywhere make the tree invalid.

Example 1

Input
root = [2,1,3]
Output
true
Explanation
1 < 2 < 3 with 1 on the left and 3 on the right.

Example 2

Input
root = [5,1,4,null,null,3,6]
Output
false
Explanation
The root's right child 4 is smaller than the root 5.

Example 3

Input
root = [5,4,6,null,null,3,7]
Output
false
Explanation
Each parent-child pair looks right, but 3 sits in the root's right subtree while being smaller than 5.

Constraints

  • 1 <= number of nodes <= 10^4
  • -2^31 <= Node.val <= 2^31 - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Validate Binary Search Tree — Solution in Python, Java & C++

Validate Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Validate Binary Search Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Problem statement

Given the root of a binary tree, decide whether it is a valid binary search tree:

  • every value in a node's left subtree is strictly smaller than the node's value;
  • every value in a node's right subtree is strictly larger than the node's value;
  • both subtrees are themselves binary search trees.

Return true if it is, false otherwise. Equal values anywhere make the tree invalid.

Example 1

Input: root = [2,1,3]
Output: true
Explanation: 1 < 2 < 3 with 1 on the left and 3 on the right.

Example 2

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root's right child 4 is smaller than the root 5.

Example 3

Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Each parent-child pair looks right, but 3 sits in the root's right subtree while being smaller than 5.

Constraints

  • 1 <= number of nodes <= 10^4
  • -2^31 <= Node.val <= 2^31 - 1

Hints for Validate Binary Search Tree

  1. Hint 1

    Comparing each node only with its two children is not enough — a value deep in a right subtree must still exceed the root.

  2. Hint 2

    Think about what an in-order traversal (left, node, right) of a valid binary search tree produces.

  3. Hint 3

    Walk the tree in order and check that every value is strictly greater than the one visited just before it; remember whether a previous value exists rather than starting from a sentinel, since values reach the 32-bit limits.

How to solve Validate Binary Search Tree

A binary tree is a binary search tree exactly when its in-order sequence is strictly increasing, so one in-order walk comparing each value with the previous one decides it.

Approach

  1. Walk the tree in order with an explicit stack: push the current node and go left until there is no left child.
  2. Pop a node. If a previous value exists and the node's value is not strictly greater, return false.
  3. Record the node's value as the previous one and continue with its right child.
  4. If the walk finishes, return true.

Why it works

In-order visits a node's whole left subtree, then the node, then its whole right subtree. If the tree is a binary search tree, the sequence is therefore increasing by induction on subtrees. Conversely, if the sequence is strictly increasing, every value of a left subtree comes before the node in the sequence and so is smaller, and every value of a right subtree comes after and is larger — which is the definition.

Complexity

  • Time — O(n)
  • Space — O(h), h the height of the tree

Pitfalls

  • Checking only left.val < node.val < right.val accepts [5,4,6,null,null,3,7].
  • Starting prev at the smallest 32-bit integer rejects a tree whose smallest value is exactly -2^31; use a flag or a wider type.
  • Duplicates are invalid: compare with <=, not <.

Reference solution

Python

from typing import Optional

def isValidBST(root: Optional[TreeNode]) -> bool:
    stack = []
    node = root
    prev = None
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        node = node.right
    return True

Java

public static boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    boolean hasPrev = false;
    int prev = 0;
    while (!stack.isEmpty() || node != null) {
        while (node != null) { stack.push(node); node = node.left; }
        node = stack.pop();
        if (hasPrev && node.val <= prev) return false;
        hasPrev = true;
        prev = node.val;
        node = node.right;
    }
    return true;
}

C++

bool isValidBST(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    bool hasPrev = false;
    int prev = 0;
    while (!stack.empty() || node) {
        while (node) { stack.push_back(node); node = node->left; }
        node = stack.back();
        stack.pop_back();
        if (hasPrev && node->val <= prev) return false;
        hasPrev = true;
        prev = node->val;
        node = node->right;
    }
    return true;
}

JavaScript

var isValidBST = function(root) {
    var stack = [], node = root, hasPrev = false, prev = 0;
    while (stack.length > 0 || node !== null) {
        while (node !== null) { stack.push(node); node = node.left; }
        node = stack.pop();
        if (hasPrev && node.val <= prev) return false;
        hasPrev = true;
        prev = node.val;
        node = node.right;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals