Design Gurus Logo
Blind 75
Validate Binary Search Tree (medium)

Problem Statement

Determine if a given binary tree is a binary search tree (BST). In a BST, for each node:

  • All nodes to its left have values less than the node's value.
  • All nodes to its right have values greater than the node's value.

Examples

Example 1:

  • Input: [5,3,7]
  • Expected Output: true
  • Justification: The left child of the root (3) is less than the root, and the right child of the root (7) is greater than the root. Hence, it's a BST.
Image

Example 2:

  • Input: [5,7,3]
  • Expected Output: false
  • Justification: The left child of the root (7) is greater than the root, making it invalid.
Image

Example 3:

  • Input: [10,5,15,null,null,12,20]
  • Expected Output: true
  • Justification: Each subtree of the binary tree is a valid binary search tree. So, a whole binary tree is a valid binary search tree.
Image

Constraints:

  • The number of nodes in the tree is in the range [1, 10<sup>4</sup>].
  • -2<sup>31</sup <= Node.val <= 2<sup>31</sup - 1

Try it yourself

Try solving this question here:

Python3
Python3