Validate a Binary Search Tree

Interview Problem Interview Medium Binary Search Tree Depth-first Search Recursion

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.isValidBST(root). Return whether every node is strictly greater than all values in its left subtree and strictly less than all values in its right subtree.

Starter code

class Solution:
    def isValidBST(self, root):
        pass

Test cases

valid

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        2,
        1,
        3
      ]
    }
  ]
}

Expected: true

Wizard outline

Step 1: Initialize Solution.isValidBST
Replace the empty starter with the first real state owned by Solution.isValidBST. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Valid case
Complete the readable core algorithm for one representative Interview case. Validate each node against lower and upper bounds inherited from every ancestor.
Step 4: Harden the Ancestor Violation boundary
Repair the reviewed boundary and pass the complete submission contract. The bounds summarize every ancestor constraint on a subtree. A node passes exactly when it lies in that interval, and recursively tightening one bound proves all descendants satisfy the global BST ordering.

Footguns and prerequisites

Comparing only with immediate children misses a descendant that violates an earlier ancestor bound.
trees and graphs

Reviewed references

LeetCode 98 — Validate Binary Search Tree

Practice prerequisites

Carry State Through Tree DFS(opens in a new tab)
Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing validate binary search tree as a complete Interview Problem.

Recommended approach and implementation

DFS with exclusive lower and upper bounds. Left receives the node value as upper; right receives it as lower.

Why it works: The bounds summarize every ancestor constraint on a subtree. A node passes exactly when it lies in that interval, and recursively tightening one bound proves all descendants satisfy the global BST ordering.

class Solution:
    def isValidBST(self, root):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        def valid(node, lower, upper):
            if node is None: return True
            if not lower < node.val < upper: return False
            return valid(node.left, lower, node.val) and valid(node.right, node.val, upper)
        return valid(root, float('-inf'), float('inf'))