Validation using bounds

What is a binary search tree?

A binary search tree, or BST, is a binary tree with an ordering rule. In the unique-key version here, every value in a node’s left subtree is smaller than that node, and every value in its right subtree is larger. This rule tells a search which direction to follow.

Example: At a node containing 8, search for 4 by moving left. Search for 12 by moving right. Search speed depends on height: an unbalanced tree can become a long chain.

Helpful before this chapter

If these ideas are new, begin with:

Binary trees

Understand the idea

Validation passes strict lower and upper bounds down the tree. Left narrows the upper bound; right narrows the lower bound. An inorder alternative checks strict increase with a correctly initialized previous value.

Work through an example

The lab deliberately changes node 3 to 5. Parent 2 permits it, but inherited high=4 rejects it.

Time and space complexity

O(n) time/O(h) stack; no need to sort or collect all keys.

Why it works

Every visited key lies strictly between all ancestor-imposed bounds.

Common mistakes

Inclusive bounds incorrectly accept duplicates under a strict policy.
Numeric sentinels must fit the key type.

Chapter lab · Python implementation

A strict BST stores smaller keys left and larger keys right. This chapter assumes unique keys; duplicate-key policies need explicit changes. Operations follow one root-to-leaf path, so their cost is proportional to height. Balancing is what turns that into a logarithmic worst-case guarantee.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

class Node:
    def __init__(self,key):
        self.key,self.left,self.right=key,None,None

def insert(root,key):
    if root is None: return Node(key)
    if key<root.key: root.left=insert(root.left,key)
    elif key>root.key: root.right=insert(root.right,key)
    return root

def search(root,key):
    while root is not None:
        if key==root.key: return root
        root=root.left if key<root.key else root.right
    return None

def valid(root,low=float('-inf'),high=float('inf')):
    if root is None: return True
    return (low<root.key<high and
            valid(root.left,low,root.key) and
            valid(root.right,root.key,high))

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=None
for x in [4,2,6,1,3]: root=insert(root,x)
assert valid(root) and search(root,3).key==3
assert search(root,9) is None
root.left.right.key=5; assert not valid(root)

CHECK YOUR UNDERSTANDING