Check whether a binary tree is a BST or not
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
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;}