Validate a BST in Python

Why it matters

Suppose someone hands you a tree and says it is a BST. How do you know? Maybe it was built by code you do not trust, or it was loaded from a file, or a bug in your insert left a value in the wrong place. A BST's speed and its answers both depend on the rule, so a check for the rule is a useful tool. It is also one of the most common interview questions on trees, and its wrong answer is a trap that catches many people who think too locally.

This lesson gives you two correct methods, explains why the obvious method fails, and shows a sentinel mistake that breaks a correct tree. It ends with a program that reads a tree from text, which is the kind of input work that real programs need.

The obvious check, and why it fails

The first idea most people have is this: for every node, check that its left child is smaller and its right child is larger. Call this the parent-child check. It looks right, because the BST rule says that smaller values go left and larger values go right.

It is wrong, and the way it is wrong teaches the most important point of this lesson. Look at this tree:

      10
     /  \
    5    15
        /  \
       6    20

Check each node against its direct children. The node 10 has 5 on the left (smaller, good) and 15 on the right (larger, good). The node 15 has 6 on the left (smaller than 15, good) and 20 on the right (larger than 15, good). The node 5 has no children, so there is nothing to check. Every parent-child pair passes.

Yet the tree is not a valid BST. The value 6 sits in the right subtree of 10, and the rule says that everything in the right subtree of 10 must be larger than 10. The value 6 is smaller than 10, so the rule is broken. The parent-child check cannot see it, because 6 and 10 are not parent and child. They are an ancestor and a deeper descendant.

The bad value is inside a subtree that looks fine when you look only at one pair of nodes. Every node has to satisfy the rule against all of its ancestors, not only against its parent.

The everyday version

Think of a school that puts children in classrooms by age, with the youngest on the left and the oldest on the right, for every row in the building. A child who is correctly placed next to a neighbour can still be in the wrong wing of the building. To check the building you must check each child against the whole wing they belong to, not only against the child beside them. A BST check must do the same thing: check each node against the whole range of values allowed at its place in the tree.

A violation the parent check misses, deep down

The trap in the earlier example had the bad value one level down. A bad value can also sit several levels down, which is harder to see by eye. Look at this three-node tree:

      20
     /
   10
     \
      25

Check the parent-child pairs first. The node 20 has 10 on the left, and 10 is smaller, so that pair passes. The node 10 has 25 on the right, and 25 is larger than 10, so that pair also passes. The parent-child check says the tree is valid.

Now check the rule for the whole tree. The value 25 sits in the left subtree of 20, because 10 and everything below it is on the left of 20. Every value in the left subtree must be smaller than 20, and 25 is not. The range method finds it this way: the root 20 gives the left child the range (-infinity, 20). The node 10 is inside that range, so it passes, and it gives its right child the range (10, 20). The value 25 is not below 20, so it fails.

The inorder method finds it too. The walk visits 10, then 25, then 20. The value 25 is larger than the value 20 that comes after it, so the sorted order breaks at that point. Both methods catch the violation, and only the parent-child check misses it.

Method 1: pass down an allowed range

Every node has a range of values that it is allowed to hold. The root may hold any value, so its range is everything from the smallest possible value to the largest. When you move to a left child, the child's range is the same as the parent's, except that the upper limit becomes the parent's value, because everything on the left must be smaller than the parent. When you move to a right child, the lower limit becomes the parent's value.

Go back to the bad tree and trace the ranges. The root 10 has range (-infinity, infinity). Its left child 5 gets (-infinity, 10), and 5 fits. Its right child 15 gets (10, infinity), and 15 fits. The left child of 15 is 6. Its range is inherited from 15 on the upper side, and from 10 on the lower side, so it is (10, 15). The value 6 is not greater than 10, so it is outside its range. The check fails, and the tree is invalid.

The recursive function below does this walk. The animation below shows the calls that pass the ranges down.

Step through the animation above. Each call carries a lo and a hi with it, like a note saying what range the node must fit into. Watch how the note changes when the walk turns left or right.

import math
 
 
def is_valid(n, lo, hi):
    if n is None:
        return True
    if n.val <= lo or n.val >= hi:
        return False
    return is_valid(n.left, lo, n.val) and is_valid(n.right, n.val, hi)
 
 
def is_valid_bst(root):
    return is_valid(root, -math.inf, math.inf)

Read the code in order. An empty subtree is valid, so the function returns True for None. A node is outside its range if its value is at or below the lower limit or at or above the upper limit. That is the <= and >= test, which also rejects duplicates, as the strict rule requires. If the node is inside its range, the function checks its left subtree with the upper limit set to the node's value, and its right subtree with the lower limit set to the node's value. Both checks must pass.

The limits are -math.inf and math.inf. math.inf is a float that is larger than every number, and -math.inf is smaller than every number. Python compares an integer with a float without trouble, so these limits sit outside the range of any value in the tree. The common mistakes section shows what goes wrong when a limit is a real number that a node can hold.

The function visits each node once, so the time is O(n). The recursion goes as deep as the tree is tall, so the extra memory is O(h), the height.

Tracing the range method on the good tree

The range method is easiest to trust when you see it run on a tree that should pass. Take the good tree with root 50, left 30 (children 20 and 40), and right 70. The table lists the range each node must fit, which the function passes down as it goes.

Look closely at the range of 40. Its lower limit is 30, because the walk went right from 30. Its upper limit is 50, because the walk went left from 50. So 40 must lie between the two ancestors where the walk turned, and it does. A value such as 35 would fit that slot, and a value such as 55 would not, because 55 is larger than 50 and so belongs in the right subtree of the root.

Every node fits, so the function returns True. The bad tree fails at one node, 6, whose range is (10, 15). The table shows the difference: a bad tree has a row where the value is outside the range, and the function stops there.

Method 2: each subtree reports its range

A third method works from the bottom up. Each call returns the smallest and the largest value in its subtree. A node is valid when the largest value on its left is below it and the smallest value on its right is above it. If a subtree breaks the rule, the call returns None to say so, and every caller passes that answer up. This is the postorder idea from the binary trees module: the children report first, and the parent decides last.

import math
 
 
# Returns (min, max) of a valid subtree, or None if the subtree breaks the rule.
def check(n):
    if n is None:
        return (math.inf, -math.inf)
    left = check(n.left)
    if left is None:
        return None
    right = check(n.right)
    if right is None:
        return None
    if n.left is not None and left[1] >= n.val:
        return None
    if n.right is not None and right[0] <= n.val:
        return None
    sub_min = n.val if n.left is None else left[0]
    sub_max = n.val if n.right is None else right[1]
    return (sub_min, sub_max)
 
 
def is_valid_bottom_up(root):
    return check(root) is not None

The empty tree returns a pair that is impossible on purpose, with the minimum above the maximum. That pair never causes a failure, because the parent only compares against the pair when the child is not None. Python's math.inf is used for the same reason as in the range method.

Run it on five trees: the good tree, the bad tree, the edge tree with -2147483648, a tree whose root 5 has a left child 5, and the empty tree. The results are:

True False True False True

The bad tree fails at the root, not at node 6. When the check reaches 15, it is fine: its left subtree gives a largest value of 6, which is below 15, and its right subtree gives a smallest value of 20, which is above 15. The subtree of 15 therefore reports the range (6, 20). At the root 10, the right subtree's smallest value is 6, which is not above 10. That one comparison fails the whole tree.

Method 3: an inorder walk must increase

The third method uses a fact from the second lesson. The inorder walk of a valid BST prints its values in strictly increasing order. So you can walk the tree in inorder and check that every value is larger than the one before it. If any value is not larger, the tree is not a valid BST.

The method keeps one piece of state, the value printed just before the current one. Call it prev. The walk goes left, checks the node, then goes right. Here is the code.

prev = None
 
 
def inorder_check(n):
    global prev
    if n is None:
        return True
    if not inorder_check(n.left):
        return False
    if prev is not None and n.val <= prev:
        return False
    prev = n.val
    return inorder_check(n.right)

The line global prev tells Python that the name prev in this function is the one defined at the top of the file. Without it, the assignment prev = n.val would make prev a local name, and the test prev is not None would raise UnboundLocalError. Before the first value is seen, prev is None, and the test prev is not None skips the comparison.

The check n.val <= prev catches any value that is equal to or smaller than the previous one, which also rejects duplicates.

Trace it on the good tree, with root 50, left 30, right 70, and 30 having children 20 and 40. The walk goes left from 50 to 30, then left to 20. Nothing is before 20, so prev becomes 20. Back at 30, the value 30 is larger than 20, so prev becomes 30. The walk goes right to 40, which is larger than 30, so prev becomes 40. Back at 50, 50 is larger than 40, and the walk goes right to 70. The sequence 20, 30, 40, 50, 70 is strictly increasing, so the function returns True.

Now the important caveat. The variable prev is global, so it keeps its value between calls. If you run inorder_check on the same tree twice without resetting prev, the second call starts with prev at 70, and the first value it sees, 20, is smaller than 70, so the check fails. The fix is to set prev = None before each fresh check. The mistakes section shows the real output of this bug.

The time is O(n) and the extra memory is O(h), the same as the range method.

Which method to use

The first two methods are correct and both cost O(n). The range method is more direct, because it checks the rule as it is written. It also reads more naturally to someone who learned the rule first. The inorder method is simpler when you already have the walk, and it is the better choice when you want to check the output of an existing inorder function. It also has a useful side effect: the sorted output is available as you go.

Neither method is faster than the other in any way that matters for a tree of any reasonable size. Pick the one that a reader of your code will understand fastest, and say in a comment which rule you are checking.

The sentinel trap

A sentinel is a special value that stands in for "no limit". The range method needs two sentinels, one for the lowest possible value and one for the highest. In Python the usual choice is -math.inf and math.inf.

Python integers have no fixed size limit, so you do not need to worry about an int overflowing. The trap appears when a sentinel is a real number that a node can hold. Here is a valid tree. The root holds 0, and its left child holds -2147483648, which is the smallest value in a 32-bit integer. The left child must be smaller than 0, and -2147483648 is smaller than 0, so the tree is valid.

Now call the range method with a 32-bit limit as the lower sentinel, which is a common habit from other languages:

root = TreeNode(0)
root.left = TreeNode(-2147483648)
print(is_valid(root, -2147483648, 2147483647))

The output is:

False

The left child gets the range (-2147483648, 0). Its value is equal to the lower limit, so the test n.val <= lo is true, and the function says the node is outside its range. The tree is wrongly rejected. Replace the sentinel with -math.inf and the same call returns True. The rule is the same in both calls. Only the sentinel changed.

Reading a tree from text

A real program often has to build the tree from input before it can check it. A common way to write a tree as text is the preorder with null markers format. You write the value of each node in preorder (node, left, right). Every missing child is written as N. That makes the text unambiguous: you can rebuild the tree from it, one token at a time. A token is one piece of the text, here a single number or a single N.

For example, the text 10 5 N N 15 6 N N 20 N N means: the root is 10. Its left child is 5, which has two missing children (N N). Its right child is 15. The left child of 15 is 6, with two missing children. The right child of 15 is 20, with two missing children. That is the bad tree from the start of the lesson.

To read this format, use a recursive function that reads the next token. If the token is N, the function returns None. Otherwise it creates a node with that value, and then reads its left subtree and its right subtree from the following tokens. The order of the reads is the preorder order, so the tokens line up.

Python has a neat way to hold the position in the token list: an iterator. An iterator is an object that hands out one item at a time and remembers where it is. iter(list_of_tokens) makes one, and next(tokens) takes the next item. Each call to next moves the position forward, so no shared index variable is needed.

def build(tokens):
    t = next(tokens)                  # read the next token and move on
    if t == "N":
        return None
    node = TreeNode(int(t))
    node.left = build(tokens)         # the next tokens describe the left subtree
    node.right = build(tokens)        # then the right subtree
    return node

A good way to picture this is a reader who reads the tree from the top, one line at a time, and each N is a note that says "nothing here".

The program below reads one line of tokens, builds the tree with this function, and checks it with the range method from earlier in the lesson. It prints valid or invalid. It needs input, so it is not marked as a run block. Type the input shown after it.

import math
 
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build(tokens):
    t = next(tokens)
    if t == "N":
        return None
    node = TreeNode(int(t))
    node.left = build(tokens)
    node.right = build(tokens)
    return node
 
 
def is_valid(n, lo, hi):
    if n is None:
        return True
    if n.val <= lo or n.val >= hi:
        return False
    return is_valid(n.left, lo, n.val) and is_valid(n.right, n.val, hi)
 
 
tokens = iter(input().split())
root = build(tokens)
print("valid" if is_valid(root, -math.inf, math.inf) else "invalid")

Type this line and press Enter:

50 30 20 N N 40 N N 70 60 N N 80 N N

The output is valid. Now type the bad tree:

10 5 N N 15 6 N N 20 N N

The output is invalid. Try one more: 0 -2147483648 N N N. The output is valid, because the lower limit is -math.inf and not a 32-bit number. The program reads one line, so the whole tree must be on that line.

The line input().split() does two things. input() reads the whole line and removes the line break at the end. split() with no arguments breaks the line at any run of spaces, so extra spaces do no harm. The result is a list of strings, and iter turns that list into the iterator that build uses.

Choosing between the three methods

All three methods do the same job in O(n) time and O(h) stack space. The differences are in how they read and in what extra information they give you.

For a course exercise, the range method is the clearest. For a program that already prints the inorder walk, the inorder check costs almost nothing extra. The bottom-up method is worth knowing because the same pattern, a child reports a summary and the parent decides, appears in many tree problems.

Integers, is and ==

Python has one kind of whole number, int, and it behaves the same whether it is stored in a variable, a list or a node. There are no separate boxed numbers, as in Java.

Python has a different trap with equality. The operator == asks whether two values are equal. The operator is asks whether two names point at the same object. For numbers, the two can disagree. CPython, the usual Python program, keeps one shared object for each small integer from -5 to 256, and makes a new object for other numbers. So is looks correct for small numbers and fails for large ones. The program below shows it. It builds the numbers with int(text) so that the interpreter cannot share them at compile time.

a = int("1000")
b = int("1000")
c = int("127")
d = int("127")
print(a == b, a is b)
print(c == d, c is d)

Its output is:

True False
True True

The first line shows that the two 1000s are equal, but they are two separate objects. The second line shows that 127 is one shared object, because it is in the small-number range. The result for 1000 depends on the Python implementation, so another version may print True True. The rule does not depend on the implementation: use == to compare numbers, and use is only for None, as the functions in this lesson do.

Common mistakes

Mistake 1: checking only direct children. This is the trap from the start of the lesson. The fix is the range method or the inorder method, both of which look past the parent.

Mistake 2: using < where the rule needs <=. The rule says that a BST has no duplicates in this course. If the check uses <, a node equal to its bound passes, and a tree with a repeated value is accepted. The test n.val <= lo is the strict version. If you want duplicates to be allowed in your own program, use < and state the policy in a comment.

Mistake 3: a sentinel that a node can hold. This is the bug in the sentinel trap section. The call with -2147483648 as the lower limit printed False for a valid tree. The fix is to use -math.inf and math.inf. The symptom is a valid tree rejected only when it holds the smallest or largest value of some fixed-size type.

Mistake 4: forgetting to reset the global prev in the inorder method. The second call on the same tree returns False, even though the tree is valid. Here is the real output of that bug, with the function from the method 3 section and the build function from the text section. The good tree is built from the text 50 30 20 N N 40 N N 70 N N each time:

print(inorder_check(build(iter("50 30 20 N N 40 N N 70 N N".split()))))
print(inorder_check(build(iter("50 30 20 N N 40 N N 70 N N".split()))))
prev = None
print(inorder_check(build(iter("50 30 20 N N 40 N N 70 N N".split()))))

The output is:

True
False
True

The second line is wrong, because the tree has not changed. prev held 70 from the first walk, so the first value of the second walk, 20, was already smaller than the stored value. The reset on the third call is the fix. Set prev = None before each check, or pass the state into the function as a parameter.

Mistake 5: a token that is not a number. The build function reads each token as a number unless it is N. A typo such as abc stops the program with this message:

ValueError: invalid literal for int() with base 10: 'abc'

The message names the bad text, which is the first clue. Look at the input, find the token, and fix it. The N marker must be written with a capital letter, because n is not treated as a missing child. The function would try int("n"), which fails with the same kind of message.

Mistake 6: too few tokens. If the tree is missing a marker, the reader runs out of tokens. The input 10 5 N 15 6, which has five tokens and needs more, produces this message at the end of a long traceback:

StopIteration

The traceback shows the nested calls of build, from the outermost to the innermost, and the last call that failed is the one that called next on an empty iterator. StopIteration is the signal that an iterator has no more items, and it has no text of its own. Count the markers. A tree with n nodes needs exactly n + 1 N markers, and a tree written with too few markers is malformed.

Debugging walkthrough

When the validator says False and you cannot see why, print the range at every node. A tiny change to the range function does this: print the node, its lower bound and its upper bound before the checks. Run it on the bad tree. The output shows you the node 6 with range (10, 15), and the reason is visible in one line.

When the validator says True for a tree you know is wrong, check the inputs to the function. Did you pass -math.inf and math.inf at the root? Did you pass the node's value as the upper bound on the left, and as the lower bound on the right? Swapping these two is the most common cause of a wrong True.

For the inorder method, print prev and the current value at each step. If the sequence is not increasing, the first decrease is the bad spot. If it is increasing on the first call and fails on later calls, the global state is the cause.

Variations and edge cases

• An empty tree. Both methods return True. An empty tree satisfies the rule vacuously.
• One node. Always valid, because there is nothing to compare.
• Duplicates. This course rejects them. Some problems allow a duplicate in the right subtree. Change <= to < on the right side only, and say so in a comment.
• Extreme values. The infinite limits handle any integer value, however large.
• One bad value among many good ones. A large tree that is valid everywhere except one node still gets a single False. Each of the three methods stops at the first failure, so an invalid tree can be rejected sooner than a valid tree can be accepted. Every method returns one answer, yes or no, and none of them says how many nodes are wrong.
• Very tall trees. The recursion depth equals the height. A chain of 1000 nodes or more can hit Python's recursion limit, as the first lesson showed. For a validator on huge trees, use an explicit stack of nodes instead of recursion.

Reading the input safely

Python's input() reads one whole line each time it is called, and it never leaves a line break behind for the next call. That avoids a trap that catches people who read numbers with one tool and lines with another. Here is a program that reads a count and then a line of text:

n = int(input())
rest = input()
print("n=%d rest=[%s]" % (n, rest))

Type 7, press Enter, then type abc def and press Enter. The output is:

n=7 rest=[abc def]

The second call read the whole line you typed, because input() had already consumed the line with the 7. The same pattern in some other languages returns an empty string first, because the line break after the number is still waiting. Python's input() does not behave that way. If you read all the input at once with sys.stdin.read(), you get one string with every line in it, and you must split it into lines yourself.

When to run a validator

Run a validator where bad data can enter the program. Good places are right after loading a tree from a file or from input, after a batch of changes made by new code, and inside tests that check the tree after each operation. Do not run it inside every insert. A full check visits every node, so a check after each of n inserts costs about n times n steps, which is far too slow for a large tree. The checks in this lesson are for testing and for input, and the tree operations themselves already keep the rule.

What to do with a tree that is not valid

A validator only reports the problem. It does not fix the tree. If a tree is invalid and you cannot trust where the bad value came from, the safest repair is to rebuild it. Walk the tree in inorder, collect the values into a sorted list, remove the duplicates, and build a new balanced tree from that list with the from_sorted function from the balancing lesson. The result is valid, and it is balanced as well.

This repair costs O(n) time and O(n) memory for the list. It is a good choice for a batch of data loaded from outside, and a poor choice for a tree that is checked after every operation. If the bad value came from a known bug, fix the bug first, so that the next run does not create the same problem again.

Real-world and interview uses

Validation is a standard interview question, usually phrased as "is this binary tree a binary search tree". The strong answer does three things: it names the parent-child trap, it gives the range method or the inorder method, and it states the cost, which is O(n) time and O(h) space. Many candidates write the parent-child check first and then discover the trap in a follow-up question. Knowing the trap in advance is a good sign.

Validation also matters in production. A program that reads a tree from a file, or that receives one from another system, should check it before it trusts the search results. A corrupt tree gives wrong answers quietly, and a check is the cheapest way to catch that before it causes harm.

Practice

1. Is the tree with root 2, left child 2 valid under the strict rule of this course? Hint: no, because equal values are rejected.

2. Write kth_smallest(root, k) that finds the k-th smallest value without a global variable. Hint: pass a list holding the count and the answer, so the helper function can change them.

def kth_smallest(root, k):
    state = [0, -1]     # state[0] = count so far, state[1] = answer
    walk(root, k, state)
    return state[1]
 
 
def walk(n, k, state):
    if n is None or state[0] >= k:
        return
    walk(n.left, k, state)
    state[0] += 1
    if state[0] == k:
        state[1] = n.val
        return
    walk(n.right, k, state)

3. Find the lowest common ancestor of two values in a BST in O(h) time. Hint: if both values are smaller than the node, go left; if both are larger, go right; otherwise the current node is the answer.

def lca(root, a, b):
    cur = root
    while cur is not None:
        if a < cur.val and b < cur.val:
            cur = cur.left
        elif a > cur.val and b > cur.val:
            cur = cur.right
        else:
            return cur
    return None

4. Write is_valid_with_duplicates(n, lo, hi) that allows equal values in the right subtree only. Hint: change the strict test on the right side, and keep the left side strict.

def is_valid_with_duplicates(n, lo, hi):
    if n is None:
        return True
    if n.val < lo or n.val >= hi:
        return False
    return is_valid_with_duplicates(n.left, lo, n.val) and is_valid_with_duplicates(n.right, n.val, hi)

5. Write is_valid_iterative(root) that does the inorder check with an explicit list as a stack instead of recursion. Hint: push all the left children, pop one node, check it against prev, then move to its right child.

def is_valid_iterative(root):
    stack = []
    cur = root
    prev = None
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if prev is not None and cur.val <= prev:
            return False
        prev = cur.val
        cur = cur.right
    return True

6. Find a tree with three nodes, root 3, left 1 and right 5, where the parent-child check says valid but the range method says invalid. Hint: put the right child's left child below 3.

7. Write count_nodes_in_range(root, lo, hi) that counts the values between lo and hi, inclusive, and skips subtrees that cannot contain any value in range. Hint: if the node's value is below lo, the left subtree is entirely below lo and can be skipped.

def count_nodes_in_range(root, lo, hi):
    if root is None:
        return 0
    if root.val < lo:
        return count_nodes_in_range(root.right, lo, hi)
    if root.val > hi:
        return count_nodes_in_range(root.left, lo, hi)
    return 1 + count_nodes_in_range(root.left, lo, hi) + count_nodes_in_range(root.right, lo, hi)

8. Build the tree from the text 20 10 N N 30 N N and say whether it is valid. Then change the text so that it is invalid and the tree has the same shape. Hint: change one value so that it crosses its bound.

9. Explain in one sentence why -math.inf fixes the sentinel trap. Hint: no real integer in the tree is below negative infinity.

10. The validator says False for a tree that you believe is valid. List three things you would check first. Hint: the bounds passed at the root, the bounds passed to each child, and the strictness of the comparison.

What you now know

• A parent-child check is not enough. Each node must lie inside the range that its ancestors allow.
• The range method passes a lower and an upper bound down the tree. Use -math.inf and math.inf as the bounds, and never a real number that a node can hold.
• The inorder method checks that the values in inorder walk are strictly increasing. Its global state must be reset before each fresh check.
• A preorder text format with N markers describes a tree in one line, and a recursive reader using an iterator rebuilds it token by token.
• Read the error messages carefully. The message names the bad token, the missing token or the stale state, and each one points to a specific fix.