Skip to content

Volume ITechnology

4.14.11 — Validate Binary Search Tree ​

LeetCode 98 · Medium · ★ Blind 75

The problem ​

Return true if the tree is a valid binary search tree:

  • Every value in a node's left subtree is less than the node.
  • Every value in its right subtree is greater.
  • Both subtrees are themselves valid search trees.

Constraints to Keep in Mind: ​

  • 1 <= Number of nodes in the tree <= 10^4
  • -2^31 <= Node.val <= 2^31 - 1
  • Note that node values can be the absolute min/max of a 32-bit signed integer.

The brute force, and where it wastes work ​

One naive approach is to check the BST property at every node by running a full DFS just to find the maximum in its left subtree and the minimum in its right subtree, then verifying left_max < node.val < right_min.

  • Why it's too slow: Finding the max/min of subtrees for every single node takes O(n) work per node, leading to O(n^2) time complexity on a degenerate tree.
  • A better slow approach: Do an in-order traversal, dump all values into an array, and check if the array is strictly sorted. This takes O(n) time but O(n) extra space to store the array. We can do it in O(h) space without building an array.

The wrong answer nearly everyone gives first ​

Check that each node is greater than its left child and less than its right child, then recurse.

That is wrong, and here is the counterexample:

     5
   /   \
  1     6
       / \
      4   7

Every parent–child pair is fine: 1 < 5, 6 > 5, 4 < 6, 7 > 6. But 4 is in the right subtree of 5 and is smaller than 5, so this is not a search tree.

The rule is about whole subtrees, not about immediate children. That distinction is the entire problem, and it is why the naive check fails.

The pattern ​

Carry the allowed range down the tree. Every node inherits a (low, high) window from its ancestors, and passes a narrower one to each child.

  • Going left, the upper bound tightens to this node's value.
  • Going right, the lower bound tightens to this node's value.

The root starts with no bounds at all, so use infinities.

        5           range (−∞, +∞)
      /   \
     1     6        left: (−∞, 5)    right: (5, +∞)
          / \
         4   7      left: (5, 6)  ← 4 fails here

The 4 arrives with a lower bound of 5, inherited from the root, and 4 is not greater than 5. Caught.

This is the information-flows-down technique from 4.14.10, and it is the clearest example of it in the chapter.

The solution ​

python
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, low, high) -> bool:  # (1)
            if not node:  # (2)
                return True                    # an empty tree is valid

            if not (low < node.val < high):  # (3)
                return False

            return (valid(node.left, low, node.val)  # (4)
                    and valid(node.right, node.val, high))

        return valid(root, float('-inf'), float('inf'))  # (5)
ts
function isValidBST(root: TreeNode | null): boolean {
  function valid(node: TreeNode | null, low: number, high: number): boolean {  // (1)
    if (!node) return true;  // (2)
    if (!(low < node.val && node.val < high)) return false;  // (3)
    return valid(node.left, low, node.val)  // (4)
        && valid(node.right, node.val, high);
  }

  return valid(root, -Infinity, Infinity);  // (5)
}

Line by line ​

(1) The helper takes a node and the range its value must lie in. Every value in this node's subtree must be strictly greater than low and strictly less than high. The range is information flowing down the tree, exactly like the "biggest so far" in 4.14.10.

(2) An empty subtree breaks no rules.

(3) Check this node against its range. Python lets you write low < node.val < high, which means "low < node.val and node.val < high". If the value is outside the range, the whole tree is invalid, so stop.

(4) Check both children with tighter ranges. Going left, every value must also be less than this node, so the upper limit becomes node.val. Going right, every value must also be greater than this node, so the lower limit becomes node.val. The other limit is passed down unchanged. That unchanged limit is what catches a value that is fine next to its parent but wrong compared with an ancestor higher up. and stops early: if the left side fails, the right side is never checked.

(5) Start with no limits at all. Minus infinity and plus infinity mean the root may hold any value. Using infinities removes every "is there a limit yet?" special case, the same trick as in 4.11.7.

Hand Trace ​

Trace on the failing counterexample tree:

  • Initial call: valid(5, -inf, inf)
  1. Node 5: -inf < 5 < inf. True.
    • Calls valid(1, -inf, 5) (left child).
    • Calls valid(6, 5, inf) (right child).
  2. Left path valid(1, -inf, 5):
    • Node 1: -inf < 1 < 5. True. Left and right are null, returns True.
  3. Right path valid(6, 5, inf):
    • Node 6: 5 < 6 < inf. True.
    • Calls valid(4, 5, 6) (left child).
    • Calls valid(7, 6, inf) (right child).
  4. Deep left path valid(4, 5, 6):
    • Node 4: 5 < 4 < 6 is False. 4 is not greater than 5.
    • Returns False.
  5. The and chain collapses, returning False for the whole tree. ✓

Strict inequalities. LeetCode's definition forbids duplicates entirely. Some definitions allow equal values on one side, so ask — it changes < to <= on one branch and the interviewer is often checking whether you notice the ambiguity.

Infinities as the starting bounds remove every boundary branch, the same trick as 4.11.7. If the values could genuinely be the largest possible integer, pass None and check for it instead.

and short-circuits, so a failure in the left subtree stops the right one being walked.

The in-order solution ​

There is a second answer, and it tells you something useful about how search trees are ordered.

An in-order traversal of a valid BST produces values in increasing order. So walk in order and check that each value is greater than the one before.

python
def isValidBST(self, root):
    self.prev = None

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

    return inorder(root)

Only the previous value is kept, not the whole list, so it is still O(h) space.

Building the full list first and then checking it sorted also works, and costs O(n) space. Fine as a first answer, then improve it.

Which to prefer? The range version is easier to explain and generalises to other "validate a property along the path" problems. The in-order version is a nice fact to know and is the natural one if you already think of a BST as a sorted sequence. Say both.

Complexity ​

  • Time Complexity: O(n). In the worst-case (a valid BST), we must visit every node exactly once to verify it. At each node, we do O(1) constant time bounds checking.
  • Space Complexity: O(h). The only extra space is the recursion call stack, which is equal to the height of the tree. This is O(\log n) for a balanced tree and O(n) for a completely unbalanced tree.

Edge cases ​

  • One node. Always valid.
  • Equal values, like a parent 2 with a left child 2. Invalid under LeetCode's rule, because the check is strict <. Some definitions allow equal values on one side, so ask.
  • Values at the 32-bit limits, like a single node holding 2^{31} - 1. Infinities as starting limits handle this. Starting limits of "the largest 32-bit number" would wrongly reject it.
  • A violation deep down against a distant ancestor, like the counterexample above. Caught by the limit passed down unchanged.

Where this goes next ​

  • Recover Binary Search Tree — exactly two nodes have been swapped; find them. In-order traversal, and the swapped pair shows up as the one or two places where the order breaks.
  • Kth Smallest Element in a BST — in-order again, stopping after k values. 4.14.12.
  • Largest BST Subtree — return, from each node, the size and the value range of its subtree, and whether it is a valid BST. Three values up instead of one.

The rule: the BST property is about subtrees, not children, so validate it by carrying a range downwards — or by using the fact that in-order gives you sorted output.

What the interviewer will push on ​

"Why is checking parent against child not enough?" Give the counterexample. This is the question the problem exists to ask, and it is the fastest way to tell who has thought about it.

"What are your starting bounds?" Infinities, so the root is unconstrained.

"Are duplicates allowed?" Ask. It changes one comparison.

"Can you do it without passing bounds?" In-order traversal, checking that values increase.

"What if the values could be the maximum integer?" Use None as the sentinel instead of infinity, and check for it.

One thing to volunteer: state the property correctly before writing anything — "every value in the left subtree, not just the left child" — and give the counterexample yourself. It shows you know where this problem's trap is.

Next: 4.14.12 Kth Smallest Element in a BST — using the sorted-order fact directly.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet