Validate a Binary Search Tree

Table of Contents +

This is a classic tree question. It trips up so many people. It looks simple. You just check left is smaller and right is bigger, right? But that is exactly the trap. The interviewer is checking if you understand what a BST really means across the whole subtree, not just one node and its two kids.

🌳 The Problem

You are given a binary tree. You have to check if it is a valid Binary Search Tree, or BST for short. A BST is a tree where, for every single node, everything in its left subtree is smaller than it, and everything in its right subtree is bigger than it.

Return true if the tree is a valid BST. Return false if it is not.

Here is what that looks like:

Tree A (valid):           Tree B (not valid):
       5                          5
      / \                        / \
     3   8                      3   8
    / \                            / \
   2   4                          4   9


Input:  Tree A   ->   Output: true
Input:  Tree B   ->   Output: false

Look closely at Tree B. The node 4 sits in the right subtree of the root 5. But 4 is smaller than 5. So it breaks the rule. The whole tree is not a valid BST. This is true even though 4 looks fine right next to its own parent 8.

🧠 The Common Mistake First

Most people write this first, and it feels correct. For each node, just check that the left child is smaller and the right child is bigger. Do that check at every node and you are done.

But that is wrong. See Tree B above. The node 8 has children 4 and 9. Both look fine. 4 is less than 8. 9 is greater than 8. So this broken check says “valid”. But it is not valid. The 4 is in the right side of the root 5, so it must be greater than 5. It is not.

So the lesson is this. A node is not just compared with its parent. It must respect every ancestor above it. The left side of 5 allows numbers below 5. The right side allows numbers above 5. That rule has to follow each node all the way down.

🎯 The Range Idea

Here is the clean way interviewers want. We give every node a range it is allowed to live in. We call this the valid (min, max) range. The node’s value must be greater than min and less than max.

Think of it like a security check at a building. The root can be any value, so its range is wide open, from negative infinity to positive infinity. Now we walk down:

  • When you go to the left child, the value must stay below the current node. So the max shrinks down to the current node’s value.
  • When you go to the right child, the value must stay above the current node. So the min rises up to the current node’s value.

Each node narrows the range for the children below it. That way an ancestor far above still controls what is allowed. This is the part the broken solution missed.

Let me show why it works on Tree B. The root 5 passes with range (-inf, +inf). We go right to 8, so the range becomes (5, +inf). Then we go left from 8 to reach 4, so the range becomes (5, 8). Now 4 must be greater than 5. It is not. So we return false. The range caught it.

Steps to validate a BST

Let’s write the steps before the code.

  1. Start at the root with the widest range: min = -infinity and max = +infinity.
  2. For the current node, check that its value is greater than min AND less than max. If not, return false.
  3. Go left: check the left subtree with the range (min, node.value).
  4. Go right: check the right subtree with the range (node.value, max).
  5. An empty node (null) is always valid, so return true for it.
  6. The tree is valid only if every node passes its own check.

Watch the equals sign

A BST usually does not allow duplicate equal values on the wrong side. So use strict checks: the value must be strictly greater than min and strictly less than max. If you use greater-than-or-equal by mistake, a tree with two equal nodes can slip through as valid.

Code to validate a BST

Now let’s see it in every language.

validate_bst.py
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


# check the node stays inside (low, high), then narrow for children
def is_valid(node, low, high):
    if node is None:
        return True  # empty node is always valid


    if node.val <= low or node.val >= high:
        return False


    # left side must be below node.val, right side must be above it
    return is_valid(node.left, low, node.val) and \
           is_valid(node.right, node.val, high)


def is_valid_bst(root):
    return is_valid(root, float("-inf"), float("inf"))


def main():
    # Tree B: root 5, right child 8, and 8 has left child 4 (invalid)
    root = Node(5)
    root.left = Node(3)
    root.right = Node(8)
    root.right.left = Node(4)  # 4 is less than the root 5
    root.right.right = Node(9)


    print("Is valid BST:", is_valid_bst(root))


if __name__ == "__main__":
    main()

The output of the above code will be:

Is valid BST: False

⏱️ Time and Space Complexity

Approach Time Space
Check only direct children (wrong) O(n) O(h)
Min-max range recursion (correct) O(n) O(h)

We visit each node one time, so the time is O(n), where n is the number of nodes. The space is O(h), where h is the height of the tree. That space comes from the recursion call stack as it goes down the tree. For a balanced tree that is O(log n). For a long skinny tree it can be O(n) in the worst case.

The inorder trick

There is another neat way. If you walk a BST with an inorder traversal (left, then node, then right), the values come out fully sorted. So you can do an inorder walk and check that each value is bigger than the one before it. If any value is not bigger, it is not a valid BST. Mention this in the interview. It shows you know your traversals.

🧩 Key Takeaways

  • ✅ A node in a BST must respect every ancestor, not just its direct parent.
  • ✅ Carry a valid (min, max) range down the tree, and narrow it at each step.
  • ✅ Going left lowers the max to the node’s value. Going right raises the min to the node’s value.
  • ✅ Use strict less-than and greater-than checks so equal duplicates do not slip through.
  • ✅ Time is O(n) and space is O(h) for the recursion stack.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why is checking only a node against its direct children wrong?

    Why: A value can look fine next to its parent but still break the range set by a grandparent or higher ancestor.

  2. 2

    When you move to the LEFT child, how does the range change?

    Why: Left-side values must stay below the current node, so the max becomes the current node's value.

  3. 3

    What does an inorder traversal of a valid BST produce?

    Why: Inorder (left, node, right) on a valid BST visits values in increasing sorted order, which gives another way to validate it.

  4. 4

    What is the time complexity of the min-max range solution?

    Why: We visit every node exactly once, so the time is O(n) where n is the number of nodes.

Score: 0 / 4

🚀 What’s Next?

Now that you can validate a BST, keep building your tree skills:

Once the range idea clicks, a whole set of tree problems starts to feel the same. Get this pattern solid and BST questions stop being scary.

Previous Lowest Common Ancestor Next Binary Tree Level Order Traversal

Share & Connect

Share on LinkedIn