← all entries
A-056● Day 562026.07.02mediumleetcode #98neetcode150

Validate Binary Search Tree

#tree#depth-first-search#binary-search-tree#binary-tree
↗ leetcode #98 · validate-binary-search-tree
01

Problem

· problem
P.056

Validate Binary Search Tree

↗ leetcode #98

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.

constraints
  • · 1 ≤ number of nodes ≤ 10⁴
  • · -2³¹ ≤ Node.val ≤ 2³¹ - 1
// paraphrased summary — see source for full text
examples
example 1input → output
[2,1,3]
true
example 2input → output
[5,1,4,null,null,3,6]
false
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Does 'strictly less than' and 'strictly greater than' mean duplicate values are not allowed?
  • ☐
    Must the entire left subtree satisfy the condition, or just the immediate left child?
  • ☐
    Should an empty tree or a single-node tree be considered valid?
  • ☐
    Can we handle nodes with negative values?
  • ☐
    Can we modify the tree structure during validation?
  • ☐
    Should we return a list of invalid nodes?
  • ☐
    Should the range (left, right) account for all possible node values?
  • ☐
    Do we need to calculate the height of the tree?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Define helper function
○
def valid(node, left, right):
○
def isValid(node):
○
def check(node, limit):
step 2· Base case: empty node│ nested
○
return True
○
return False
○
return node is not None
step 3· Validate current node in range│ nested
○
if not (left < node.val < right):
○
if not (left <= node.val <= right):
○
if node.val < left and node.val > right:
step 4· Validate left subtree│ nested
○
return valid(node.left, left, node.val) and valid(
○
valid(node.left, left, node.left)
○
valid(node.left, node.val, right)
step 5· Validate right subtree│ nested
○
node.right, node.val, right
○
valid(node.right, node.right, right)
○
valid(node.right, left, node.val)
step 6· Start recursion with infinite bounds
○
return valid(root, float("-inf"), float("inf"))
○
return valid(root, 0, float('inf'))
○
return valid(root, float('-inf'), 0)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def isValidBST(self, root: TreeNode) -> bool:
9
        def valid(node, left, right):
10
            if not node:
11
                return True
12
            if not (left < node.val < right):
13
                return False
14
15
            return valid(node.left, left, node.val) and valid(
16
                node.right, node.val, right
17
            )
18
19
        return valid(root, float("-inf"), float("inf"))
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[2,1,3]
→
true
case 2
[5,1,4,null,null,3,6]
→
false
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.