Trees — Binary Trees, Traversals, BSTs and Heaps

Terminology

A tree is a connected acyclic graph; a rooted tree designates one node as the root.

Binary trees

Each node has at most two children, left and right.

Counting facts

• At most $2^i$ nodes at level $i$; at most $2^{h+1} - 1$ nodes in a tree of height $h$.
• With $n$ nodes, height is between $\lceil\log_2(n+1)\rceil - 1$ and $n - 1$.
• $n_0 = n_2 + 1$: leaves exceed degree-2 nodes by one. A full binary tree with $i$ internal nodes has $i + 1$ leaves and $2i + 1$ nodes.
• A binary tree with $n$ nodes has $n - 1$ edges and $n + 1$ None child pointers.
• Number of distinct binary tree shapes with $n$ nodes: Catalan $C_n = \frac{1}{n+1}\binom{2n}{n}$ — 1, 2, 5, 14, 42.

Representations

• Linked: Node(val, left, right).
• Array (ideal for complete trees, e.g. heaps): with 0-based indexing, children of $i$ are at $2i + 1$ and $2i + 2$, and the parent at $\lfloor(i - 1)/2\rfloor$.

Traversals

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

def preorder(t):
    return [t.val] + preorder(t.left) + preorder(t.right) if t else []

def inorder(t):
    return inorder(t.left) + [t.val] + inorder(t.right) if t else []

def postorder(t):
    return postorder(t.left) + postorder(t.right) + [t.val] if t else []

from collections import deque
def levelorder(t):
    out, q = [], deque([t] if t else [])
    while q:
        node = q.popleft()
        out.append(node.val)
        q.extend(c for c in (node.left, node.right) if c)
    return out

Reconstruction: in-order together with pre-order (or post-order) determines a binary tree uniquely when keys are distinct — the first (or last) element is the root, which splits the in-order sequence into the left and right subtrees. Pre-order plus post-order alone does not determine a general binary tree (it does for full binary trees).

Binary search trees

BST property: for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger.

def search(t, key):
    while t and t.val != key:
        t = t.left if key < t.val else t.right
    return t

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

• Search, insert and delete cost $O(h)$: $O(\log n)$ when balanced, $O(n)$ in the worst case (inserting sorted keys builds a skewed "linked list").
• Delete: a leaf is removed; a node with one child is replaced by that child; a node with two children takes its in-order successor's key, and the successor is deleted.
• Minimum = leftmost node; maximum = rightmost node; in-order traversal = sorted keys.
• Self-balancing trees (AVL, red–black) keep $h = O(\log n)$ with rotations.

Binary heaps and priority queues

A binary min-heap is a complete binary tree in which every parent is $\le$ its children, so the minimum is at the root. Stored in an array.

import heapq
h = [9, 4, 7, 1, 8]
heapq.heapify(h)              # O(n) → [1, 4, 7, 9, 8]
heapq.heappush(h, 3)          # O(log n)
smallest = heapq.heappop(h)   # 1
top3 = heapq.nsmallest(3, [5, 1, 8, 3, 9])   # [1, 3, 5]
# max-heap: push negated keys

Priority queues drive Dijkstra's algorithm (see graph algorithms), event simulation, top-$k$ selection and scheduling.

Expression trees

Internal nodes are operators and leaves are operands. Pre-, in- and post-order traversals give prefix, infix and postfix expressions; evaluating the tree is a post-order traversal.

Quick revision