Validate Binary Search Tree

Problem

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

Examples

The brute-force approach

For each node, collect all values in its left subtree and right subtree. Check that all left values are < node.val and all right values are > node.val.

def get_all(node):
    if not node: return []
    return [node.val] + get_all(node.left) + get_all(node.right)

def is_valid(node):
    if not node: return True
    left_vals = get_all(node.left)
    right_vals = get_all(node.right)
    if any(v >= node.val for v in left_vals): return False
    if any(v <= node.val for v in right_vals): return False
    return is_valid(node.left) and is_valid(node.right)

O(n²) — repeated subtree collection for each node.

Spotting the pattern

This is a Tree Traversal problem. The key question to ask yourself:

Why is checking left.val < node.val < right.val at each node NOT enough to validate a BST? What counter-example would pass that check but fail the real BST property?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.