Blind 75 / Trees / Validate Binary Search Tree

Validate Binary Search Tree

MediumTrees
Asked byAmazonBloombergFacebookMicrosoftAdobeQualtrics

Problem

Given the root of a binary tree, determine whether it is a valid binary search tree — every node's left subtree contains only values strictly less than the node, and every right subtree contains only values strictly greater.

Examples

Example 1
Input:root = [2,1,3]
Output:true
Example 2
Input:root = [5,1,4,null,null,3,6]
Output:false
The right subtree of 5 has a node (3) less than 5.

Constraints

  • The number of nodes is in the range [1, 10^4].

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Trees pattern

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Look for this pattern when

  • The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
  • You need level-by-level information (BFS) versus depth-first structural information (DFS).

Read the full Trees guide →

Video walkthroughs

Original problem on LeetCode ↗

More Trees problems

← Binary Tree Level Order TraversalKth Smallest Element In a Bst →