From Parent Comparisons to Range Propagation: How I Derived the Validate BST Solution During an Interview ( Leetcode 98 )

Binary Search Tree validation is one of those problems that looks simple at first.

My initial instinct was straightforward:

• Traverse the tree
• Check whether the left child is smaller than its parent
• Check whether the right child is greater than its parent

That sounds correct, but it misses an important part of the BST definition.

In this post, I will walk through how I moved from that first idea to the correct range-based solution, the mistakes I made, the Python concepts I learned, and the interview lessons that came from the process.

The First Idea

My first thought was to validate each node using only its immediate children.

Parent
├── Left child < Parent
└── Right child > Parent

For a simple tree, this works.

      5
     / \
    3   7

Here:

3 < 5
7 > 5

So the tree is valid.

The problem appears when the tree becomes deeper.

The Counterexample

Consider this tree:

        5
       / \
      3   7
         /
        4

Looking only at node 7:

4 < 7

That local relationship is correct.

However, node 4 is inside the right subtree of 5.

That means it must also satisfy:

4 > 5

It does not.

Therefore, the tree is invalid.

This is where the main insight appeared:

A node must satisfy the rules created by all of its ancestors, not only its parent.

The Real BST Rule

Instead of asking:

Is this node valid compared with its parent?

we should ask:

Is this node valid within the range allowed by all of its ancestors?

Each node receives a valid interval:

(min_allowed, max_allowed)

The node must satisfy:

min_allowed < node.val < max_allowed

The inequalities must be strict because duplicate values are not allowed in a valid BST.

Starting With the Root

The root has no ancestor restrictions.

Its valid range is:

(-∞, +∞)

In Python:

float("-inf")
float("inf")

So the first queue entry is:

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

Why Fixed Integer Bounds Are Risky

At first, I thought about using values such as:

0 to INT_MAX

That fails immediately for negative values.

Using:

INT_MIN
INT_MAX

is better, but it can still create awkward edge cases when node values are equal to those exact limits.

Using infinity is cleaner:

float("-inf")
float("inf")

This allows every valid integer value without requiring special handling.

What the Queue Stores

A normal BFS queue might contain only nodes:

deque([root])

That is not enough here because each node has a different valid range.

Instead, each queue entry contains:

(node, min_allowed, max_allowed)

So the queue is initialized as:

queue = deque([
    (root, float("-inf"), float("inf"))
])

How the Bounds Change

The most important part of the solution is understanding how to update the range for each child.

Left Child

A left child must be smaller than the current node.

The inherited lower bound remains unchanged.

The current node becomes the new upper bound.

Current node range: (min_allowed, max_allowed)

Left child range: (min_allowed, node.val)

Idea :

min_allowed < left child < node.val

The queue entry becomes:

(node.left, min_allowed, node.val)

Right Child

A right child must be greater than the current node.

The inherited upper bound remains unchanged.

The current node becomes the new lower bound.

Current node range: (min_allowed, max_allowed)

Right child range:(node.val, max_allowed)

Idea :

node.val < right child < max_allowed

The queue entry becomes:

(node.right, node.val, max_allowed)

The Validation Step

Each time a node is removed from the queue, validate it immediately.

if not (min_allowed < node.val < max_allowed):
    return False

An equivalent version is:

if node.val <= min_allowed or node.val >= max_allowed:
    return False

The chained comparison is shorter and directly represents the allowed interval.

Python Tuple Unpacking

Each queue item is a tuple with three values.

A longer way to read it would be:

item = queue.popleft()

node = item[0]
min_allowed = item[1]
max_allowed = item[2]

Python tuple unpacking makes this cleaner:

node, min_allowed, max_allowed = queue.popleft()

This assigns all three values in one line.

Appending the Child State

One small syntax mistake I made was trying to write:

queue.append(node.left, min_allowed, node.val)

This does not work because append() accepts one object.

We want that one object to be a tuple:

queue.append((node.left, min_allowed, node.val))

The outer parentheses belong to append().

The inner parentheses create the tuple.

Complete Algorithm

1. If the root is None:
   return True

2. Add the root to the queue with range:
   (-∞, +∞)

3. While the queue is not empty:

   a. Remove:
      (node, min_allowed, max_allowed)

   b. Check:
      min_allowed < node.val < max_allowed

   c. If the check fails:
      return False

   d. If the left child exists:
      add it with:
      (min_allowed, node.val)

   e. If the right child exists:
      add it with:
      (node.val, max_allowed)

4. If every node is valid:
   return True

Complete Code

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

        # An empty tree is considered a valid BST.
        if not root:
            return True

        # Each queue entry contains:
        # (node, minimum allowed value, maximum allowed value)
        queue = deque([
            (root, float("-inf"), float("inf"))
        ])

        while queue:
            node, min_allowed, max_allowed = queue.popleft()

            # The node must satisfy all ancestor constraints.
            if not (min_allowed < node.val < max_allowed):
                return False

            # Left child keeps the lower bound.
            # The current node becomes its upper bound.
            if node.left:
                queue.append(
                    (node.left, min_allowed, node.val)
                )

            # Right child keeps the upper bound.
            # The current node becomes its lower bound.
            if node.right:
                queue.append(
                    (node.right, node.val, max_allowed)
                )

        return True

Complexity Analysis

Time Complexity

O(n)

Every node is added to the queue once, removed once, and validated once.

A common mistake is to say O(log n) because BST operations are often associated with logarithmic complexity.

However, this algorithm validates the entire tree.

In the worst case, every node must be examined.

Therefore:

Time complexity: O(n)

Space Complexity

O(n)

The queue may contain an entire level of the tree.

For a balanced tree, the final level can contain roughly half of all nodes.

Therefore, the worst-case auxiliary space is:

Space complexity: O(n)

Interview Lessons

1. Local correctness does not guarantee global correctness

The parent-child comparisons were locally correct, but they did not preserve restrictions from earlier ancestors.

Whenever a tree problem involves ordering, paths, or inherited rules, ask:

Does this node depend only on its parent,
or does it depend on the entire path above it?

2. Use a counterexample to challenge the first idea

The tree:

        5
       / \
      3   7
         /
        4

quickly proves that local comparisons are insufficient.

In an interview, producing or understanding a counterexample is valuable because it shows that you are testing your reasoning instead of defending an incorrect idea.

3. Carry useful state during traversal

The queue does not have to store only nodes.

It can store extra information:

(node, min_allowed, max_allowed)

This pattern appears in many tree and graph problems.

Examples include:

• Tracking depth
• Tracking path sums
• Tracking parent information
• Tracking valid ranges
• Tracking visited state
• Tracking distance from the source

4. Explain why one bound changes

For the left child:

The lower bound stays the same.
The parent value becomes the new upper bound.

For the right child:

The upper bound stays the same.
The parent value becomes the new lower bound.

This explanation is more important than memorizing the tuple order.

5. Be careful with strict inequalities

The correct condition is:

min_allowed < node.val < max_allowed

Not:

min_allowed <= node.val <= max_allowed

Allowing equality would incorrectly permit duplicate values.

6. Do not assume every BST problem is O(log n)

Searching in a balanced BST can be O(log n).

Validating the entire BST requires visiting every node:

O(n)

Always analyze the work performed by the actual algorithm.

Final Takeaway

I did not begin with the perfect solution.

I started with a reasonable local comparison approach.

A counterexample showed why it failed.

That led to the realization that each node needs a range created by all of its ancestors.

Once that range was included in the BFS queue, the rest of the solution became systematic:

Root: (-∞, +∞)

Left child:

(min_allowed, parent.val)

Right child:

(parent.val, max_allowed)

That is the most valuable part of the problem.

The goal in an interview is not always to recognize the final algorithm immediately.

The goal is to test your assumptions, learn from counterexamples, and gradually build the correct solution.

Easy peasy , now in the comments lets discuss some similar problem : D