Start learning free

LESSON 408 OF 536 · BINARY TREES

Validate Binary Search Tree in Python: Passing Bounds Down

Practice O(n) Read the full explanation

Given the root of a binary tree, return True if it is a valid binary search tree (BST), and False otherwise.

A binary tree is a valid BST when, for every node:

  • every value in its left subtree is strictly smaller than the node's value,
  • every value in its right subtree is strictly larger than the node's value.

The rule is about the whole subtree, not only the children: a node's value must also fit every node above it.

The trees below are written in level order (top to bottom, left to right), with None for a missing child.

 

Example 1:

     2
    / \
   1   3

Input: root = [2,1,3]
Output: True
Explanation: 1 is smaller than 2 and 3 is larger.

Example 2:

     5
    / \
   1   4
      / \
     3   6

Input: root = [5,1,4,None,None,3,6]
Output: False
Explanation: The right child of the root 5 is 4, which is smaller than 5.

Example 3:

     5
    / \
   4   6
      / \
     3   7

Input: root = [5,4,6,None,None,3,7]
Output: False
Explanation: Every node is in order with its own children: 4 < 5 < 6 and 3 < 6 < 7. But 3 is in the right subtree of 5, where every value must be larger than 5. Comparing each node only with its children misses this: each node must lie in the range that all of its ancestors set.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • Each node value is between -231 and 231 - 1.
  • The tree is at most 800 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, visiting each node once.

Node values can be the smallest and the largest 32-bit integers, so a bound that means "no limit yet" can't be one of those values.

STEP 1 OF 6
    Ctrl + Enter to check

    PYTHON · BINARY TREES

    Validate Binary Search Tree in Python, explained

    Problem overview

    The method isValidBST(root) receives the root of a binary tree and returns True when it is a valid binary search tree. For every node, all values in its left subtree must be strictly smaller than the node's value, and all values in its right subtree strictly larger. The rule covers the whole subtree, not only the two children, so a node's value must also fit every node above it. The lesson provides the TreeNode class, with val, left and right, as shown in a comment in the starter code.

    The tree [2, 1, 3] is valid. The tree [5, 1, 4, None, None, 3, 6] is not, because the right child of 5 is 4, which is smaller. The tree [5, 4, 6, None, None, 3, 7] is not valid either, and it is the instructive one. Each node is in order with its own children: 4 < 5 < 6, and 3 < 6 < 7. But 3 sits in the right subtree of 5, where every value must be larger than 5.

    Approach: every node lives inside a range

    Comparing each node only to its children, as the third example shows, misses violations that involve a grandparent or something further up. The fix is to carry the information down. Each node must lie strictly between a low and a high bound that its ancestors set.

    • The root has no ancestors, so it has no bounds: both are None.
    • Going into the left child of a node with value v, the upper bound becomes v and the lower bound stays what it was.
    • Going into the right child, the lower bound becomes v and the upper bound stays what it was.

    The bounds are None and not a very small or large number because node values may be as small and as large as the 32-bit integer limits: any number picked to mean "no limit" could itself be a value in the tree. With None, "no bound on this side" can't be confused with a real value.

    For [5, 4, 6, None, None, 3, 7] the helper visits the nodes with these bounds:

    node 5, low None, high None
node 4, low None, high 5
node 6, low 5, high None
node 3, low 5, high 6

    The node 3 has to be larger than 5 and smaller than 6, which no value can be, so the check fails there and the answer is False. Each node is visited at most once, so the time is O(n).

    Step by step

    1. In isValidBST, call the helper on root with None for both bounds and return its answer.
    2. Declare the helper validate(self, node, low, high). It returns True when every value in the tree under node is larger than low and smaller than high, where a None bound limits nothing.
    3. Empty tree: if not node, return True. An empty tree breaks no rule, and this is also where the recursion ends below a leaf.
    4. Lower bound: if low is not None and node.val <= low, return False. The comparison is "less than or equal" because values must be strictly larger, so a value equal to the bound is a violation too. When low is None, and stops before the comparison.
    5. Upper bound: likewise, if high is not None and node.val >= high, return False.
    6. Recurse: return the and of two calls. The left subtree gets low and node.val, the right subtree gets node.val and high.

    The solution in Python

    class Solution:
    def validate(self, node, low, high):
        if not node:
            return True
        if low is not None and node.val <= low:
            return False
        if high is not None and node.val >= high:
            return False
        return self.validate(node.left, low, node.val) and self.validate(node.right, node.val, high)

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.validate(root, None, None)

    Python details:

    • Use is not None for the bounds, not truthiness. A bound can be 0, which is falsy. Writing if low and node.val <= low would skip the check for a bound of 0 and accept invalid trees. The comparison with None asks only the question that matters.
    • not node is fine for the node itself, because a TreeNode object is always truthy and None is falsy.
    • Short-circuit and. If the left subtree is already invalid, the right one isn't searched.
    • No integer limits. Python integers have no fixed size, so values at the 32-bit extremes need no special care. The None bounds matter for correctness of the idea, not because of overflow.

    Complexity

    The time is O(n): each node is checked once, with constant work. The space is the recursion stack, O(h) for a tree of height h, which is O(n) for a chain.

    Edge cases and common mistakes

    • Comparing only with children. This accepts [5, 4, 6, None, None, 3, 7], which is invalid.
    • Allowing equal values. [2, 2, 2] returns False: a duplicate of the node on either side breaks the strict rule. Using < instead of <= in the checks would accept it.
    • Using a number for "no bound". The values -2147483648 and 2147483647 are allowed in a tree. A tree such as [-2147483648] is valid, and so is [2147483647, -2147483648], and a made-up limit can reject one of them.
    • A single node is always valid.
    • A valid-looking subtree in a bad place. [10, 5, 15, None, None, 6, 20] returns False because 6 is in the right subtree of 10 but smaller than it.

    Testing

    tree (level order)result
    [2, 1, 3]True
    [5, 1, 4, None, None, 3, 6]False
    [5, 4, 6, None, None, 3, 7]False
    [2, 2, 2]False
    [1]True
    [-2147483648]True
    [2147483647, -2147483648]True
    [10, 5, 15, None, None, 6, 20]False
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free