Problem · Canonical Warm-Up
mediumbounds · recursion · in-orderTime · O(n)Space · O(h)

Validate Binary Search Tree

Problem walkthrough: statement, hints, solution, mistakes

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys strictly less than the node's key.
  • The right subtree of a node contains only nodes with keys strictly greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Examples

     2
    / \
   1   3
Input: root = [2,1,3]  -> true

       5
      / \
     1   4
        / \
       3   6
Input: root = [5,1,4,null,null,3,6]  -> false
(root's right child is 4 < 5)
← Back to Recursion as Structural InductionAll modules →