Validate Binary Search Tree

Medium · Trees

You are given the root of a binary tree. Determine whether it satisfies the binary search tree property: for every node, all values in its left subtree must be strictly smaller than the node's value, and all values in its right subtree must be strictly larger. Return true if the whole tree obeys this rule everywhere, or false if any node breaks it, even if the violation involves a node further down the tree rather than a direct child.

Examples

Input:  root = [2,1,3]
Output: true
Why:    Every left descendant is smaller than 2 and every right descendant is larger, so the ordering rule holds everywhere.

Input:  root = [5,1,4,null,null,3,6]
Output: false
Why:    The node with value 4 has a left child 3 and right child 6, which fits locally, but 4's right subtree also contains 3, which is smaller than 5's left subtree bound, breaking the global order.

Input:  root = [1,1]
Output: false
Why:    A duplicate value violates the strict less-than/greater-than requirement between a node and its subtrees.

Constraints

the tree has between 1 and 10^4 nodes, and each node value fits in a 32-bit signed integer

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Validate Binary Search Tree

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Validate Binary Search Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.