Facebook PixelValidate Binary Search Tree — Coding Practice
Validate Binary Search TreeMedium

Validate Binary Search Tree

Medium 14.8k33% acceptance
TreeDepth-First SearchBinary Search TreeBinary Tree

Given the root of a binary tree, determine whether it is a valid binary search tree (BST).

A BST requires that for every node, all values in its left subtree are strictly less than the node's value, all values in its right subtree are strictly greater, and both subtrees are themselves valid BSTs.

Return true if the tree is a valid BST, false otherwise. The tree is given in level-order (TreeNode with { val, left, right }, null for a missing child).

Example 1
Input: root = [2,1,3]
Output: true
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
4 sits in the right subtree of 5 but is less than 5, so the BST rule is broken.
Example 3
Input: root = [5,4,6,null,null,3,7]
Output: false
3 is in the right subtree of 5 yet smaller than 5 — a local parent/child check would miss this; a range check catches it.
Constraints
  • The number of nodes is in the range [1, 10⁴].
  • -2³¹ ≤ Node.val ≤ 2³¹ - 1
Asked atAmazonMicrosoftMetaBloomberg
JavaScript
Loading editor…
Case 1
[2,1,3]
expected: true
Case 2
[5,1,4,null,null,3,6]
expected: false
Case 3
[5,4,6,null,null,3,7]
expected: false
Case 4
[1]
expected: true
Case 5
[2,2,2]
expected: false
Case 6
[10,5,15,3,7,12,20]
expected: true
Case 7
[3,1,5,0,2,4,6]
expected: true