Check whether a binary tree is a BST or not

Medium

Problem

Return true if the binary tree is a valid binary search tree: every value in a node's left subtree is strictly smaller than the node, every value in its right subtree is strictly larger, and both subtrees are valid BSTs.

Example 1

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

Example 2

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

3 is in 5’s right subtree but is smaller than 5.

Also asked as: validate bst · check for BST · Check if a tree is a BST or not

Test cases

Case 1

Input:    [2,1,3]
Expected: true

Case 2

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

Case 3

Input:    [5,4,6,null,null,3,7]
Expected: false

Case 4

Input:    [2,2,2]
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Recurse with min/max bounds

Time O(n)Space O(h)

Every node must lie strictly between the bounds inherited from its ancestors.

function isValidBST(node, lo = -Infinity, hi = Infinity) {
if (!node) return true;
if (node.val <= lo || node.val >= hi) return false;
return isValidBST(node.left, lo, node.val) && isValidBST(node.right, node.val, hi);
}

2. In-order traversal must be strictly increasing

Time O(n)Space O(h)

An in-order walk of a BST visits values in sorted order; check each value is larger than the previous.

function isValidBST(root) {
let prev = -Infinity, ok = true;
const dfs = (n) => {
if (!n || !ok) return;
dfs(n.left);
if (n.val <= prev) ok = false;
prev = n.val;
dfs(n.right);
};
dfs(root);
return ok;
}