98. Validate Binary Search Tree

On LeetCode ->

Reformulated question¶

Given a binary tree, return whether it is a valid BST:

every node in the left subtree is < node.val
every node in the right subtree is > node.val
both subtrees must also satisfy the rule

Example:

input: [5,1,4,null,null,3,6]
output: False
why: 3 is in the right subtree of 5, so it must be > 5, but it is not

Key trick¶

Do not compare a node only with its parent.

Track the full valid range for each node:

left child must be in (low, node.val)
right child must be in (node.val, high)

Trap¶

Common mistakes:

checking only left.val < node.val < right.val
forgetting that constraints come from all ancestors, not just the parent
allowing duplicates even though BST here is strictly < and >
using truthiness for bounds, which breaks on 0

Example of the last bug:

if low and node.val <= low:

This fails when low == 0.

Why is this question interesting?¶

It looks local, but the property is global.

It tests whether you can turn a tree invariant into recursive state.

Solve the problem with idiomatic Python¶

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode], low: Optional[int], high: Optional[int]) -> bool:
            if node is None:
                return True

            # Node value must stay strictly inside ancestor bounds.
            if low is not None and node.val <= low:
                return False
            if high is not None and node.val >= high:
                return False

            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)

        return dfs(root, None, None)

Alternative exact-same-idea view:

inorder traversal of a valid BST is strictly increasing

class SolutionInorder:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None

        def inorder(node: Optional[TreeNode]) -> bool:
            nonlocal prev
            if node is None:
                return True
            if not inorder(node.left):
                return False
            if prev is not None and node.val <= prev:
                return False
            prev = node.val
            return inorder(node.right)

        return inorder(root)

Standard iterative inorder:

class SolutionInorderIterative:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack = []
        prev = None
        node = root

        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()

            if prev is not None and node.val <= prev:
                return False

            prev = node.val
            node = node.right

        return True

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([2, 1, 3], True),
        ([5, 1, 4, None, None, 3, 6], False),
        ([5,4,9,None,None,8,11,None,None,None,None,6,None,10,12], True), # added by myself
        ([2, 2, 3], False),
        ([2, 1, 2], False),
        ([10], True),
        ([5, 4, 6, None, None, 3, 7], False),
        ([0, -1], True),
        ([32, 26, 47, 19, None, None, 56, None, 27], False),
    ],
)
def test_is_valid_bst(values, expected):
    root = build_tree(values)
    assert Solution().isValidBST(root) is expected

Comment my solution¶

Good:

you used the right overall idea: pass min/max constraints down the tree
your tests already cover the important non-local violations

Problems:

if strict_min and ... and if strict_max and ... are wrong for bound 0
direct child checks are redundant once range checks are correct
debug print(...) should be removed
_isValidBST should have a -> bool return type
one test is wrong: [5,1,4] is not the standard tree from the prompt; to model that example you need [5,1,4,None,None,3,6]

from __future__ import annotations

from collections import deque
from dataclasses import dataclass
from typing import Optional

import pytest


@dataclass
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


def build_tree(values: list[Optional[int]]) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None

    nodes = [None if v is None else TreeNode(v) for v in values]

    for i, node in enumerate(nodes):
        if node is None:
            continue

        left_i = 2 * i + 1
        right_i = 2 * i + 2

        if left_i < len(nodes):
            node.left = nodes[left_i]

        if right_i < len(nodes):
            node.right = nodes[right_i]

    return nodes[0]


class Solution:
    def _isValidBST(self, node: Optional[TreeNode], strict_min: Optional[int], strict_max: Optional[int]):
        if node is None:
            return True

        left = node.left
        right = node.right
        val = node.val

        if strict_min and val <= strict_min:
            print(f"wrong: node {node} can't be on the right subtree of node {strict_min}")
            return False
        if strict_max and val >= strict_max:
            print(f"wrong: node {node} can't be on the left subtree of node {strict_max}")
            return False

        if left and left.val >= val:
            return False
        if right and right.val <= val:
            return False

        return self._isValidBST(left, strict_min, val) and self._isValidBST(right, val, strict_max)


    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self._isValidBST(root, None, None)

## Test

import pytest

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([2], True),
        ([1, 1, None], False),
        # ([1, None, 1], False),
        ([2,1,3], True),
        ([5,1,4], False),
        ([5,4,9,None,None,8,11,None,None,None,None,6,None,10,12], True),
        # Because 4 is not > 5.
        # It should because it's on the right subtree of 5
        ([5,4,9,None,None,3,11], False),
        # Because 10 is not < 9.
        # It should because it's on the left subtree of 9
        ([5,4,9,None,None,8,11,None,None,None,None,6,10,None,None], False),
    ],
)
def test_isValidBST(values, expected):
    root = build_tree(values)
    assert Solution().isValidBST(root) == expected

Minimal fix:

class Solution:
    def _isValidBST(
        self,
        node: Optional[TreeNode],
        strict_min: Optional[int],
        strict_max: Optional[int],
    ) -> bool:
        if node is None:
            return True

        val = node.val

        if strict_min is not None and val <= strict_min:
            return False
        if strict_max is not None and val >= strict_max:
            return False

        return (
            self._isValidBST(node.left, strict_min, val)
            and self._isValidBST(node.right, val, strict_max)
        )

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self._isValidBST(root, None, None)

About iterative in order implementation:

Good:

nice attempt to simulate recursive inorder traversal explicitly
the key invariant is correct: visited values must be strictly increasing
it does produce inorder order on many cases

Issues:

stack = [root] breaks if root is None
# root is never None is not true for the LeetCode signature
creating node_without_left = TreeNode(...) is unusual and costly
it allocates new nodes, so traversal is no longer read-only
copying only val and right works here, but it is a fragile way to encode traversal state
is_bst is unnecessary; returning early is simpler

Main style point:

iterative inorder is usually done by pushing the whole left chain, not by rebuilding nodes

Your version is clever, but less idiomatic than the standard stack approach.

class SolutionInorderIterative:
    # Implemented myself (Tony Aldon) to verify I understand
    # correctly the above in order traversal
    # it passes the same tests.
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # root is never None
        prev = None
        is_bst = True
        stack = [root]

        while (is_bst and stack):
            node = stack.pop()
            if node.left:
                node_without_left = TreeNode(val=node.val, left=None, right=node.right)
                stack.append(node_without_left)
                stack.append(node.left)
                continue
            if prev is not None and prev >= node.val:
                is_bst = False
                continue
            prev = node.val
            if node.right:
                stack.append(node.right)
        return is_bst

Code¶

from __future__ import annotations

from dataclasses import dataclass
from typing import Optional

import pytest


@dataclass
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


def build_tree(values: list[Optional[int]]) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None

    nodes = [None if v is None else TreeNode(v) for v in values]

    for i, node in enumerate(nodes):
        if node is None:
            continue

        left_i = 2 * i + 1
        right_i = 2 * i + 2

        if left_i < len(nodes):
            node.left = nodes[left_i]
        if right_i < len(nodes):
            node.right = nodes[right_i]

    return nodes[0]


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode], low: Optional[int], high: Optional[int]) -> bool:
            if node is None:
                return True

            # Keep the valid range coming from all ancestors.
            if low is not None and node.val <= low:
                return False
            if high is not None and node.val >= high:
                return False

            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)

        return dfs(root, None, None)


class SolutionInorder:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None

        def inorder(node: Optional[TreeNode]) -> bool:
            nonlocal prev
            if node is None:
                return True
            if not inorder(node.left):
                return False
            if prev is not None and node.val <= prev:
                return False
            prev = node.val
            return inorder(node.right)

        return inorder(root)

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([2, 1, 3], True),
        ([5, 1, 4, None, None, 3, 6], False),
        ([2, 2, 3], False),
        ([2, 1, 2], False),
        ([10], True),
        ([5, 4, 6, None, None, 3, 7], False),
        ([0, -1], True),
        ([32, 26, 47, 19, None, None, 56, None, 27], False),
    ],
)
def test_is_valid_bst(values, expected):
    root = build_tree(values)
    assert Solution().isValidBST(root) is expected
    assert SolutionInorder().isValidBST(root) is expected


build_tree([2, 1, 3])
Solution().isValidBST(build_tree([2, 1, 3]))
Solution().isValidBST(build_tree([5, 1, 4, None, None, 3, 6]))
Solution().isValidBST(build_tree([0, -1]))