Ordering invariant

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

The ordering invariant applies to every descendant, not only immediate children. All keys in the left subtree are smaller than the root; all in the right subtree larger under our unique-key convention.

Work through an example

Root 4 cannot have 5 anywhere in its left subtree, even if 5 is correctly right of node 2 locally.

Time and space complexity

Search follows O(h) nodes, worst O(n) in an unbalanced tree.

Why it works

Every ancestor contributes a bound to descendant keys.

Common mistakes

Checking only parent-child pairs misses ancestor violations.
Duplicate behavior must be specified.

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