- Traverse a binary tree in preorder, inorder, postorder and level order
- Search, insert and delete in a binary search tree and explain the O(h) cost
- Trace heap insertion and extract-min on the array representation
The folders on your computer, a family tree, the HTML elements of a web page, the syntax tree a compiler builds from a program — all of these are trees. In a hospital emergency room patients are seen not in order of arrival but by urgency: that is a priority queue, built on a tree. In this lesson we study the mathematics of trees and their two most important kinds — the binary search tree and the heap.
Binary trees and traversals
A tree in which every node has at most two children (left and right). The top node is the root; a node without children is a leaf. A node's depth is the number of edges from the root to it, and the tree's height h is the largest depth.
- nnumber of nodes
- hheight of the tree (in edges)
Depth d holds at most 2ᵈ nodes: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. So a binary tree with n nodes cannot be lower than about log₂ n, but it can be as tall as n − 1.
50
/ \
30 70
/ \ / \
20 40 60 80
/
35| Traversal | Rule | Result for the example tree | Where it is used |
|---|---|---|---|
| Preorder | root, left, right | 50 30 20 40 35 70 60 80 | copying a tree |
| Inorder | left, root, right | 20 30 35 40 50 60 70 80 | getting the keys in sorted order |
| Postorder | left, right, root | 20 35 40 30 60 80 70 50 | deleting, computing folder sizes |
| Level order | with a queue, top to bottom | 50 30 70 20 40 60 80 35 | shortest paths, printing by levels |
Binary search trees (BST)
In a binary search tree, for every node all keys in its left subtree are smaller and all keys in its right subtree are larger. A search starts at the root: go left if the key is smaller, right if it is larger — the tree version of binary search. Insertion follows the same path to an empty spot. Both operations take O(h) time.
Delete 30 from the example tree. What is the inorder traversal afterwards?
Show solutionHide solution
30 has two children (20 and 40). Right subtree: 40 → 35. Its smallest key is 35 (keep going left).
Write 35 in place of 30 and remove 35 from its old place (it is a leaf).
New tree: 50 → (35 → 20, 40), (70 → 60, 80).
Inorder: 20 35 40 50 60 70 80 — still increasing, so the BST property holds.
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)
else:
root.right = insert(root.right, key)
return root
def inorder(t):
return inorder(t.left) + [t.key] + inorder(t.right) if t else []
def preorder(t):
return [t.key] + preorder(t.left) + preorder(t.right) if t else []
def height(t):
return -1 if t is None else 1 + max(height(t.left), height(t.right))
root = chain = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
for k in range(1, 9):
chain = insert(chain, k)
print('inorder: ', inorder(root))
print('preorder:', preorder(root))
print('height:', height(root), '| sorted input height:', height(chain))▸ Expected output
inorder: [20, 30, 35, 40, 50, 60, 70, 80] preorder: [50, 30, 20, 40, 35, 70, 60, 80] height: 3 | sorted input height: 7
The way out is balanced trees: after each insertion and deletion they use rotations to keep the height O(log n). In an AVL tree the heights of every node's left and right subtrees differ by at most 1 (h < 1.44 log₂ n); in a red-black tree h ≤ 2 log₂(n + 1). Java's TreeMap and C++'s std::map are red-black trees, and database indexes are B-trees holding hundreds of keys per node.
Heaps and priority queues
A complete binary tree (all levels full, the last one filled from left to right) in which every node is less than or equal to its children. So the minimum is always at the root. The tree is stored without pointers, simply in an array.
- iindex of the node in the array (from 0)
The tree is written into the array level by level; being complete, it leaves no gaps and its height is ⌊log₂ n⌋.
Min-heap: [3, 5, 8, 10, 7]. a) Insert 2. b) Then extract the minimum. Write the array after each step.
Show solutionHide solution
parent(5) = 2 holds 8 > 2 → swap → [3, 5, 2, 10, 7, 8].
parent(2) = 0 holds 3 > 2 → swap → [2, 5, 3, 10, 7, 8]. We reached the root.
b) Sift-down: take the root 2, move the last element 8 to the root → [8, 5, 3, 10, 7].
Children: 5 (i = 1) and 3 (i = 2); the smaller is 3 → swap → [3, 5, 8, 10, 7].
i = 2 has no children (indexes 5 and 6 are outside the array) → [3, 5, 8, 10, 7], extracted 2.
Each operation makes at most h = ⌊log₂ n⌋ swaps → O(log n).
import heapq
heap = [3, 5, 8, 10, 7]
heapq.heappush(heap, 2)
print(heap)
print(heapq.heappop(heap), heap)
patients = []
for urgency, name in [(3, 'Aysel'), (1, 'Murad'), (2, 'Leyla'), (1, 'Elvin')]:
heapq.heappush(patients, (urgency, name))
while patients:
print(heapq.heappop(patients))
def heap_sort(a):
h = a[:]
heapq.heapify(h)
return [heapq.heappop(h) for _ in range(len(h))]
print(heap_sort([9, 4, 7, 1, 8, 2]))▸ Expected output
[2, 5, 3, 10, 7, 8] 2 [3, 5, 8, 10, 7] (1, 'Elvin') (1, 'Murad') (2, 'Leyla') (3, 'Aysel') [1, 2, 4, 7, 8, 9]
heapq module is a min-heap on a plain list: the result matches our hand trace. Patients are stored as (urgency, name) pairs: a smaller number is more urgent, and ties are broken by name. heapify + n times heappop = heap sort.- hheight of a node above the leaves
- n / 2ʰ⁺¹n / 2ʰ⁺¹number of nodes of height h (about)
heapify turns an array into a heap bottom-up: half the nodes are leaves (0 work), a quarter sink 1 step, and so on. Since ∑ h/2ʰ = 2, the total is O(n), not O(n log n). Heap sort then does n extractions for O(n log n).
| Operation | Balanced BST | Unbalanced BST (worst) | Binary heap |
|---|---|---|---|
| search for any key | O(log n) | O(n) | O(n) |
| insert | O(log n) | O(n) | O(log n) |
| peek at the minimum | O(log n) | O(n) | O(1) |
| extract the minimum | O(log n) | O(n) | O(log n) |
| build from n elements | O(n log n) | O(n²) | O(n) |
Key points
- A binary tree with n nodes has height at least ≈ log₂ n and at most n − 1.
- Preorder, inorder, postorder say where the root goes; the inorder traversal of a BST lists the keys in increasing order.
- BST operations are O(h); balanced trees (AVL, red-black, B-trees) keep h = O(log n).
- A heap is a complete tree stored in an array: children at 2i + 1 and 2i + 2; insert and extract-min are O(log n), building is O(n).
- A priority queue is built with a heap; heap sort is O(n log n), in place, but not stable.
Check yourself
10 questions. Every correct answer earns XP.