Problem

Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST).

A BST follows three important rules:

• Every node in the left subtree must have a value less than the current node.
• Every node in the right subtree must have a value greater than the current node.
• Both the left and right subtrees must also be valid BSTs.

Example 1

    2
   / \
  1   3

Input: [2,1,3]
Output: True

This satisfies all BST rules.

Example 2

    1
   / \
  2   3

Input: [1,2,3]
Output: False

The left child (2) is greater than its parent (1), violating the BST property.

My Initial Thought Process

At first, I thought validating a BST simply meant checking whether:

• the left child is smaller than the parent
• the right child is larger than the parent

Unfortunately, this isn't enough.

Consider this tree:

        5
       / \
      3   7
         /
        4

If we only compare each node with its parent:

• 7 > 5 ✅
• 4 < 7 ✅

Everything appears correct.

However, 4 is inside the right subtree of 5, so it should also be greater than 5.

Since 4 < 5, this tree is not a valid BST.

This is the key insight of the problem:

Every node must satisfy constraints imposed by all of its ancestors, not just its parent.

The Better Idea: Carry the Valid Range

Instead of comparing each node only with its parent, we keep track of the range of values each node is allowed to have.

Initially, the root can be any value:

(-∞, +∞)

Whenever we go left:

upper = current node value

Whenever we go right:

lower = current node value

For example:

         8
       /   \
      3     10
     / \
    1   6

The ranges become:

8  -> (-∞, +∞)

3  -> (-∞, 8)

10 -> (8, +∞)

1  -> (-∞, 3)

6  -> (3, 8)

Notice how node 6 is constrained by both its parent (3) and the root (8).

DFS Solution

We perform a depth-first traversal while carrying two values:

• lower → smallest allowed value
• upper → largest allowed value

At every node we simply verify:

lower < node.val < upper

If this fails, the tree is not a BST.

Otherwise we continue searching both children with updated bounds.

Python Solution

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def dfs(node, lower, upper):
            if not node:
                return True

            valid = lower < node.val < upper

            return (
                valid
                and dfs(node.left, lower, node.val)
                and dfs(node.right, node.val, upper)
            )

        return dfs(root, float("-inf"), float("inf"))

Dry Run

Consider:

        5
       / \
      3   7
         /
        6

Start with

dfs(5, -∞, +∞)

Root (5)

-∞ < 5 < +∞ ✅

Left subtree:

dfs(3, -∞, 5)

Right subtree:

dfs(7, 5, +∞)

Node 3

Allowed range:

(-∞, 5)

-∞ < 3 < 5 ✅

Both children are None.

Node 7

Allowed range:

(5, +∞)

5 < 7 < +∞ ✅

Left child:

dfs(6, 5, 7)

Node 6

Allowed range:

(5, 7)

5 < 6 < 7 ✅

Everything passes.

Return:

True

Now consider this invalid tree:

        5
       / \
      3   7
         /
        4

When we visit node 4, the valid range is:

(5, 7)

Checking:

5 < 4 < 7 ❌

The recursion immediately returns False.

Why This Works

Every recursive call narrows the valid interval.

Going left updates the upper bound.

Going right updates the lower bound.

This guarantees that every node satisfies the BST property with respect to every ancestor, not just its immediate parent.

Time Complexity

Each node is visited exactly once.

Time Complexity: O(n)

where n is the number of nodes.

Space Complexity

The recursion stack depends on the height of the tree.

• Balanced BST: O(log n)
• Skewed BST: O(n)

Key Takeaways

• Comparing a node with only its parent is not sufficient.
• Every node must satisfy constraints inherited from all its ancestors.
• Passing a valid (lower, upper) range during DFS elegantly enforces the BST rules.
• This is the standard interview solution and is both simple and optimal.

Once you recognize that every node has an allowable range rather than just a parent relationship, the entire problem becomes much easier to reason about.