Validate Binary Search Tree — Medium Coding Interview Question

Given the root of a binary tree, determine if it is a valid binary search tree (BST): every node's left subtree contains only values strictly less than the node's value, and every right subtree contains only values strictly greater, recursively.

Example

Input: root = [2,1,3]

Output: true

Constraints

• The number of nodes is in the range [1, 10⁴]

Topics & Companies

Topics: trees, binary-search

Asked by: Amazon, Meta, Microsoft, Google, Bloomberg

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(h).

Practice more

• All DSA Problems
• DSA Patterns