codejump
MediumPythonJavaScriptTypeScript

Binary Tree — Validate a BST

Data StructuresTreesDFSBinary Search Tree

solve(levelOrder) receives a binary tree serialized level by level, with
null for a missing child (the same format LeetCode uses). A helper that
builds the tree is already provided. Return true when the tree is a valid
binary search tree.

Valid means: for *every* node, all values in its left subtree are strictly
smaller and all values in its right subtree are strictly larger. Comparing a
node with only its direct children is the classic wrong answer.

Examples

solve([2, 1, 3])                      → true
solve([5, 1, 4, null, null, 3, 6])    → false   // 4 is smaller than the root 5
solve([5, 4, 6, null, null, 3, 7])    → false   // 3 sits in 5's right subtree
solve([2, 2, 2])                      → false   // duplicates are not allowed
solve([])                             → true    // an empty tree is valid

Hint on the shape of the answer: pass an allowed (min, max) range down the
recursion and narrow it at every step.

Sample tests

Test #1A minimal valid BST
Input: [[2,1,3]]
Output: true
Test #2Right child 4 is smaller than the root 5
Input: [[5,1,4,null,null,3,6]]
Output: false
Test #33 is a valid child of 6 but breaks the root's bound
Input: [[5,4,6,null,null,3,7]]
Output: false