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¶

from utils import TreeNode
from typing import Optional

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

from utils import TreeNode
from typing import Optional

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:

from utils import TreeNode
from typing import Optional

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¶

from utils import tree_build
from typing import Optional
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 = tree_build(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 utils import TreeNode, tree_build
from typing import Optional
import pytest

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)


@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 = tree_build(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