How It Works

This chapter traces small examples by hand: tree traversals, BST insert, search and delete, and the heap operations sift up, sift down and heapify. The example tree is the BST you get by inserting 50, 30, 70, 20, 40, 60, 80 in that order.

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

Four traversals

A traversal visits every node once. The three depth-first traversals differ only in when the node itself is visited.

Use pre-order to copy or serialize a tree, in-order to read a BST in sorted order, and post-order when a parent's value depends on its children (folder sizes, freeing a tree). Level-order is breadth-first search with a queue.

from collections import deque


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 preorder(n):
    return [n.key] + preorder(n.left) + preorder(n.right) if n else []


def inorder(n):
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []


def postorder(n):
    return postorder(n.left) + postorder(n.right) + [n.key] if n else []


def level_order(root):
    out, queue = [], deque([root] if root else [])
    while queue:
        n = queue.popleft()
        out.append(n.key)
        if n.left:
            queue.append(n.left)
        if n.right:
            queue.append(n.right)
    return out


root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, k)
print(preorder(root), inorder(root), postorder(root), level_order(root), sep="\n")

BST search and insert

To find 60, compare with 50 (larger, go right to 70), then with 70 (smaller, go left to 60), and you are done after three comparisons. Searching for 65 stops at the empty right child of 60 and reports "not found". Insertion attaches the new node at exactly that empty spot, so inserting 65 makes it the right child of 60.

Three cases of BST deletion

Deletion depends on how many children the node has.

• No children (20): simply detach it.
• One child: lift that child into the deleted node's place.
• Two children (30): find the minimum of the right subtree, the in-order successor (40), copy its key into the node, then delete the successor from the right subtree. The successor has no left child, so that second delete is one of the easy cases.

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root


root = delete(root, 30)
print(inorder(root), preorder(root))
# [20, 40, 50, 60, 70, 80] [50, 40, 20, 70, 60, 80]

Heap insert: sift up

Insert 0 into the min-heap [1, 3, 2, 7, 4, 5]. To keep the complete shape, append it at the end (index 6), then swap it with its parent while it is smaller.

Removing the minimum: sift down

Remove the root (0), move the last element (2) to the root, then swap it with its smaller child until it settles.

Heapify: building a heap in one pass

Pushing n items one by one costs O(n log n). Running sift down from the last internal node (index n // 2 - 1) back to the root builds a heap in O(n), because most nodes sit near the bottom and only move a little.

def sift_down(a, i, n):
    while True:
        small, l, r = i, 2 * i + 1, 2 * i + 2
        if l < n and a[l] < a[small]:
            small = l
        if r < n and a[r] < a[small]:
            small = r
        if small == i:
            return
        a[i], a[small] = a[small], a[i]
        i = small


def heapify(a):
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))
        print(f"i={i}: {a}")


heapify([9, 5, 7, 1, 3, 2])
# i=2: [9, 5, 2, 1, 3, 7]
# i=1: [9, 1, 2, 5, 3, 7]
# i=0: [1, 3, 2, 5, 9, 7]

Summary

The three depth-first traversals differ only in when the node is visited, and level-order uses a queue. A BST search or insert walks down one side per comparison, and a node with two children is deleted by replacing it with its in-order successor. A heap stays valid with just two moves, sift up after appending and sift down after replacing the root, and heapify runs sift down bottom-up to build a heap in O(n).