v9.1.1
Menu

Validate Binary Search Tree

mediumPROTrees & GraphsGoogle DSA

Given the root of a binary tree (as a level-order array), determine if it is a valid binary search tree (BST).

A valid BST has:

  • Left subtree contains only nodes with keys less than the node's key
  • Right subtree contains only nodes with keys greater than the node's key
  • Both subtrees must also be valid BSTs

Example

Input
2,1,3
Output
True
Reasoning
  • The input array 2,1,3 represents a binary tree with root node 2, left child 1, and right child 3.
  • We check the left subtree: since 1 is less than 2, it satisfies the BST condition.
  • We check the right subtree: since 3 is greater than 2, it satisfies the BST condition.
  • Both subtrees are valid BSTs (as they are single nodes with no children), so the entire tree is a valid binary search tree, resulting in an output of True.

Constraints

  • 1 <= number of nodes <= 10^4
  • -2^31 <= Node.val <= 2^31 - 1

More from Google DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.