Search, insert, and delete

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

Search compares then selects one subtree. Insert adds at a missing position. Delete handles leaf, one-child, and two-child cases; replace a two-child key with its inorder successor, then delete that successor.

Work through an example

Deleting 4 in the lab can replace it with successor 6, then remove the old 6 node. Deleting 2 uses successor 3 from its right subtree.

Time and space complexity

O(h) operation time; recursive forms O(h) stack.

Why it works

Every changed link preserves the ancestor bounds and keeps all other keys reachable.

Common mistakes

Returning a new subtree root requires reconnecting it to the parent.
Successor replacement must remove the original successor.

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