AI Hints
Home›DSA in Python Tutorial›Tree Practice
DSA in Python · Lesson 68 of 132

Practice: Validate a BST

Checking the rule everywhere.

⏱ 2 min read▶ Video at 1:20:09🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Given a binary tree, check whether it's a valid binary search tree. It's tempting to just check each node against its two children. But that's a trap. Pause, and think about why.

Practice: Validate a BST
From the video: Practice: Validate a BST
  • Is it a valid BST?
  • Checking children isn't enough
  • Why not?

Passing down limits

The rule must hold for the whole subtree, not just the children. So we pass down the allowed range. Going left, the node's value becomes the new upper limit. Going right, it becomes the new lower limit. Run it. Our sample tree passes. The broken tree fails, because six sits in eight's right subtree, even though it's smaller than eight.

validate.pypython
from tree import sample, TreeNode

def valid(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not low < node.value < high:
        return False
    return valid(node.left, low, node.value) and valid(node.right, node.value, high)

broken = TreeNode(8, TreeNode(3), TreeNode(10, TreeNode(6), TreeNode(12)))
print(valid(sample()))
print(valid(broken))
Output
True
False
Also uses tree.py
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def sample():
    return TreeNode(8,
        TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
        TreeNode(10, None, TreeNode(14, TreeNode(13))))

PICTURE = '        8\n      /   \\\n     3     10\n    / \\      \\\n   1   6      14\n      / \\    /\n     4   7  13'

Another way

There's a neat second solution. An in order traversal of a valid binary search tree is sorted. So you can list the values in order, and check that each one is bigger than the one before. Both ways are O of N.

keyvalue
Pass limitslow < value < high
Or in ordercheck it's sorted
Traponly checking children
CostO(n)

Summary

Validate a binary search tree by passing down the allowed range, or by checking that in order is sorted. Next, finding the shared ancestor of two nodes.

Key takeaways
  • Pass low and high
  • Left: new high
  • Right: new low
Next up: Practice: Lowest Common Ancestor — where two paths meet