Trees & Binary Trees

Discrete Mathematics — Session 5 · Full Course v2 · Parts II–III

Notes By Pr. El Hadiq Zouhair

1 / 21

Outline — Trees & Binary Trees

Part II — Trees

Tree = acyclic connected graph.
Equivalent characterisations (5 conditions).
$n$ vertices $\Rightarrow n - 1$ edges (proved).
Rooted trees, terminology.
Spanning trees.

Part III — Binary trees

Python representation $[]$ & $[a, L, R]$.
Recursive functions: size, height, leaves.
Traversals: pre/in/post-order, BFS.
Binary search tree (BST); search, insert, delete.
Binary heap, heapsort.
Balanced trees (AVL preview).
Expression trees; tree as a special graph.

References: Rosen 8e §§11.1–11.5; CLRS ch. 6, 12–13.

2 / 21

Part II

Trees

Tree = acyclic connected graph · five equivalent characterisations · spanning trees.

3 / 21

14. Tree — formal definition

A tree is a connected undirected graph that contains no cycle. A graph with no cycles (possibly disconnected) is a forest; a forest is a disjoint union of trees.

For a graph $T$ on $n$ vertices, the following are equivalent:

$T$ is a tree (connected and acyclic);
$T$ is connected and has exactly $n - 1$ edges;
$T$ is acyclic and has exactly $n - 1$ edges;
Every two vertices are joined by a unique path;
$T$ is acyclic, but adding any edge between two existing vertices creates exactly one cycle.

(1 ⇒ 2): induction on $n$. Base $n = 1$: $0 = n - 1$ edges. Step: a tree with $n \geq 2$ vertices contains a leaf $\ell$ (vertex of degree $1$); removing $\ell$ gives a tree on $n - 1$ vertices with $n - 2$ edges (by IH), so $T$ has $n - 1$ edges.
(2 ⇒ 3): if $T$ had a cycle, removing one edge would keep it connected (contradicting that a connected graph needs $\geq n - 1$ edges).
(3 ⇒ 4): connectedness + acyclicity gives uniqueness; if two distinct paths existed, their symmetric difference would contain a cycle.
(4 ⇒ 5): adding edge $\{u,v\}$ creates a cycle = existing $u$–$v$ path + new edge.
(5 ⇒ 1): all hypotheses of (1) are restated. $\square$

Rosen 8e §11.1; Diestel §1.5.

4 / 21

15. Tree properties — leaves, paths

Every tree with $n \geq 2$ vertices has at least two leaves (vertices of degree $1$).

Suppose at most one leaf. Then $\sum_v \deg(v) \geq 1 \cdot 1 + 2(n - 1) = 2n - 1$. But by the handshake lemma, $\sum_v \deg(v) = 2(n - 1) = 2n - 2$. Contradiction. $\square$

A rooted tree is a tree together with a distinguished vertex $r$ — the root. Every other vertex has a unique parent (the next vertex on the unique path to the root); vertices closer to the root are ancestors, further are descendants. Vertices with no children are leaves; the others are internal.

Term	Definition
Depth of $v$	Length of the path from root to $v$.
Height of $v$	Length of the longest path from $v$ to a leaf below it.
Height of tree	Height of the root = depth of the deepest leaf.
Level $k$	All vertices at depth $k$.

Rosen 8e §11.1.

5 / 21

16. Spanning trees

Every connected graph contains a spanning tree.

Start with $T = G$. While $T$ has a cycle, remove any edge of any cycle — connectivity is preserved (the edge can be replaced by the rest of the cycle). The process terminates with $T$ a tree. $\square$

Cayley's formula. The number of distinct spanning trees of the complete graph $K_n$ is $n^{n-2}$.

Proof techniques include Prüfer sequences (an explicit bijection between trees on $\{1, \ldots, n\}$ and sequences in $\{1, \ldots, n\}^{n-2}$), the matrix-tree theorem (determinant of the Laplacian), and double-counting (multinomials).

For $n = 4$, $4^{4-2} = 16$ spanning trees of $K_4$. Direct enumeration confirms this.

BFS or DFS from any vertex produce a spanning tree of a connected graph as a byproduct — the "BFS-tree" or "DFS-tree" used in many algorithmic problems.

Cayley (1889); Prüfer (1918); Kirchhoff (1847).

6 / 21

Part III

Binary trees

Python [] and [a, L, R] representation · traversals · BST · heap.

7 / 21

17. Binary tree — inductive definition

A binary tree $T$ is defined recursively:

The empty tree, written $\varnothing$ or [], is a binary tree.
If $a$ is a value and $L, R$ are binary trees, then $\bigl[a,\, L,\, R\bigr]$ is a binary tree with root value $a$, left subtree $L$, and right subtree $R$.

Python convention. A binary tree is a Python list:

[] denotes the empty tree;
[a, L, R] denotes a non-empty tree with root a and subtrees L and R.

This three-element-list convention matches the inductive definition exactly and supports every recursive operation cleanly.

Python — example tree # The tree # 1 # / \ # 2 3 # / \ \ # 4 5 6 T = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]] def est_vide(T): return T == [] def racine(T): return T[0] def gauche(T): return T[1] def droite(T): return T[2] print(racine(T), racine(gauche(T)), racine(droite(T))) # 1 2 3

SICP §2.2; classical nested-list representation of trees.

8 / 21

18. Recursive functions on binary trees

Every recursive function on a binary tree follows the same pattern: a base case for $\varnothing$, and a recursive case for $[a, L, R]$ that combines results from $L$ and $R$.

Python — fundamental tree functions def taille(T): """Number of nodes.""" if T == []: return 0 a, L, R = T return 1 + taille(L) + taille(R) def hauteur(T): """Height = longest root-to-leaf path. Convention: hauteur([]) == -1, hauteur([a,[],[]]) == 0.""" if T == []: return -1 a, L, R = T return 1 + max(hauteur(L), hauteur(R)) def feuilles(T): """Number of leaves.""" if T == []: return 0 a, L, R = T if L == [] and R == []: return 1 return feuilles(L) + feuilles(R) def somme(T): """Sum of all node values (assuming numeric values).""" if T == []: return 0 a, L, R = T return a + somme(L) + somme(R)

A binary tree with $n$ internal nodes has $n + 1$ leaves (in the "full" variant where every internal node has exactly two children).

SICP §2.2.2; Knuth, TAOCP, vol. 1, §2.3.

9 / 21

19. Tree traversals — pre/in/post-order

Three classical depth-first traversals visit each node exactly once:

Preorder: root, left, right.
Inorder: left, root, right.
Postorder: left, right, root.

Python — all three traversals def prefixe(T): if T == []: return [] a, L, R = T return [a] + prefixe(L) + prefixe(R) def infixe(T): if T == []: return [] a, L, R = T return infixe(L) + [a] + infixe(R) def postfixe(T): if T == []: return [] a, L, R = T return postfixe(L) + postfixe(R) + [a] T = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]] print(prefixe(T)) # [1, 2, 4, 5, 3, 6] print(infixe(T)) # [4, 2, 5, 1, 3, 6] print(postfixe(T)) # [4, 5, 2, 6, 3, 1]

Inorder = sorted for a binary search tree (next slide).
Postorder is the order needed to evaluate an arithmetic-expression tree.
Preorder matches the Polish prefix notation.

Knuth, TAOCP, vol. 1, §2.3.

10 / 21

20. Level-order traversal (BFS)

A fourth, breadth-first traversal visits nodes level by level.

Python — level-order (BFS) on a binary tree from collections import deque def parcours_largeur(T): if T == []: return [] resultat = [] file = deque([T]) while file: N = file.popleft() if N == []: continue a, L, R = N resultat.append(a) file.append(L) file.append(R) return resultat T = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]] print(parcours_largeur(T)) # [1, 2, 3, 4, 5, 6]

A perfect binary tree of height $h$ has $2^{h+1} - 1$ nodes, of which $2^h$ are leaves. Its level-order traversal corresponds exactly to the heap-indexing scheme used in arrays.

For a binary tree with $n$ nodes, the height satisfies $h \geq \lceil \log_2(n+1) \rceil - 1$. Equality is reached by perfectly balanced trees.

Knuth, TAOCP, vol. 1, §2.3.

11 / 21

21. Binary search trees (BST)

A binary search tree (BST) is a binary tree in which, for every node $[a, L, R]$:

every value in $L$ is strictly less than $a$;
every value in $R$ is strictly greater than $a$.

Equivalently, the inorder traversal yields a strictly increasing sequence.

Python — BST membership and insertion def appartient(T, x): if T == []: return False a, L, R = T if x == a: return True if x < a: return appartient(L, x) return appartient(R, x) def inserer(T, x): if T == []: return [x, [], []] a, L, R = T if x < a: return [a, inserer(L, x), R] if x > a: return [a, L, inserer(R, x)] return T # duplicate, ignored # Build a BST from a list import functools A = functools.reduce(inserer, [5, 3, 8, 1, 4, 7, 9], []) print(infixe(A)) # [1, 3, 4, 5, 7, 8, 9] ← sorted!

BST search, insert and delete all run in $O(h)$ time where $h$ is the tree height. For a balanced BST, $h = \Theta(\log n)$ — operations are logarithmic.

Knuth, TAOCP, vol. 3, §6.2.2; CLRS ch. 12.

12 / 21

22. BST deletion — three cases

Removing a value $x$ from a BST has three cases, depending on the children of the node containing $x$.

Leaf: replace the node by $\varnothing$.
One child: splice the child into the node's position.
Two children: replace the node's value by the smallest value in $R$ (the inorder successor), then recursively remove that value from $R$.

Python — BST deletion def minimum(T): a, L, R = T return minimum(L) if L != [] else a def supprimer(T, x): if T == []: return [] a, L, R = T if x < a: return [a, supprimer(L, x), R] if x > a: return [a, L, supprimer(R, x)] # x == a if L == []: return R # case 1 + 2 if R == []: return L # case 2 m = minimum(R) # case 3 return [m, L, supprimer(R, m)] A = [5, [3, [1, [], []], [4, [], []]], [8, [7, [], []], [9, [], []]]] print(infixe(supprimer(A, 3))) # [1, 4, 5, 7, 8, 9]

Without balancing (AVL, red-black, splay), repeated insertions of a sorted sequence degenerate the BST into a "vine" of height $n$ — operations slow to $\Theta(n)$. Balanced variants guarantee $\Theta(\log n)$ worst-case.

CLRS ch. 12–13.

13 / 21

23. Binary heap (min-heap)

A min-heap is a complete binary tree in which every parent's value is $\leq$ its children's values (so the minimum sits at the root). A max-heap reverses the inequality.

Stored as an array: the root is at index $1$ (or $0$); for a node at index $i$, the left child is at $2i$ (or $2i+1$) and the right child is at $2i + 1$ (or $2i + 2$). Parent: $i // 2$ (or $(i - 1) // 2$).

Python — using heapq import heapq tas = [] for x in [5, 2, 8, 1, 6, 3]: heapq.heappush(tas, x) print(tas) # [1, 2, 3, 5, 6, 8] — heap-ordered while tas: print(heapq.heappop(tas), end=' ') # 1 2 3 5 6 8 — sorted output

Insertion (heappush) and extraction (heappop) on a binary heap of $n$ elements run in $O(\log n)$ time. Building a heap from $n$ elements takes $O(n)$ via Floyd's bottom-up heapify.

Heapsort. Build a max-heap of the input ($O(n)$), then repeatedly extract the max ($O(n \log n)$). Total: $O(n \log n)$ in-place sort.

Williams (1964); Floyd (1964); CLRS ch. 6.

14 / 21

24. Balanced trees — AVL, red-black (preview)

An AVL tree is a BST where for every node the heights of the left and right subtrees differ by at most $1$ — the balance factor is in $\{-1, 0, +1\}$.

An AVL tree of $n$ nodes has height $h = O(\log n)$. Insertions and deletions trigger at most $O(\log n)$ "rotations" to restore the balance invariant.

Operation	BST (worst)	AVL / RB
Search	$\Theta(n)$	$\Theta(\log n)$
Insert	$\Theta(n)$	$\Theta(\log n)$
Delete	$\Theta(n)$	$\Theta(\log n)$
Inorder traversal	$\Theta(n)$	$\Theta(n)$

Self-balancing BSTs are cultural knowledge: students should know they exist and provide $\Theta(\log n)$ guarantees, even if the internal rotation details may be out of scope. C++ std::map and Python's SortedDict are typical industrial implementations (often red-black trees).

Adelson-Velsky & Landis (1962); CLRS ch. 13.

15 / 21

25. Tree as a special graph — bridging Parts I & III

Every tree on $n$ vertices is a connected acyclic graph with $n - 1$ edges (Part II §14). A binary tree is the rooted version with at most two ordered children per node (Part III §17).

Python — convert between the two representations def binaire_vers_graphe(T, prefixe=''): """Convert a binary tree (nested list) into a graph (dict) with synthetic vertex IDs to avoid value collisions.""" G = {} def parcours(N, vid): if N == []: return None a, L, R = N G[vid] = set() G.setdefault(vid, set()) for sous_arbre, suffix in [(L, 'L'), (R, 'R')]: sid = vid + suffix if parcours(sous_arbre, sid) is not None: G[vid].add(sid) G[sid].add(vid) return vid parcours(T, prefixe) return G T = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]] G = binaire_vers_graphe(T) print(len(G), len(G[''])>0) # 6 True # Apply any graph algorithm of Part I — BFS, DFS, connectivity — to G.

All graph algorithms of Part I (BFS, DFS, Dijkstra on a positively-weighted tree, etc.) apply directly to the converted representation. In particular, in a tree:

BFS from any vertex gives the unique distance function.
The diameter (longest path) can be found by two consecutive BFS from any vertex.
Dijkstra on a tree degenerates to a single pass — every path is unique.

Folklore tree-diameter algorithm.

16 / 21

26. Application — expression trees

An arithmetic expression like $(3 + 4) \cdot (5 - 2)$ has a natural binary-tree representation: internal nodes are operators, leaves are operands.

Python — evaluate an expression tree # Expression: (3 + 4) * (5 - 2) expr = ['*', ['+', [3, [], []], [4, [], []]], ['-', [5, [], []], [2, [], []]]] def evaluer(T): if T == []: raise ValueError('empty tree') a, L, R = T if L == [] and R == []: return a # leaf — operand g, d = evaluer(L), evaluer(R) return {'+': g + d, '-': g - d, '*': g * d, '/': g / d}[a] print(evaluer(expr)) # 21 print(prefixe(expr)) # ['*', '+', 3, 4, '-', 5, 2] ← Polish notation print(postfixe(expr)) # [3, 4, '+', 5, 2, '-', '*'] ← Reverse Polish (RPN)

The same tree, traversed three ways, gives:

Preorder = Polish prefix notation: * + 3 4 - 5 2.
Inorder (with parens) = the human-readable expression: ((3 + 4) * (5 - 2)).
Postorder = Reverse Polish notation (RPN): 3 4 + 5 2 - * — exactly the order needed for a stack-based evaluator.

Knuth, TAOCP, vol. 1, §2.3; SICP §2.3.

17 / 21

30. Summary — Parts II & III (Trees & Binary Trees)

Trees = connected acyclic graphs. Five equivalent characterisations proved.
Every tree has $n - 1$ edges; at least $2$ leaves (for $n \geq 2$).
Rooted-tree terminology: root, parent, child, depth, height, leaves.
Spanning trees: every connected graph has at least one; $K_n$ has $n^{n-2}$ (Cayley).
Binary trees: inductive definition; Python [] and [a, L, R] representation.
Recursive functions: taille, hauteur, feuilles, somme.
Traversals: preorder, inorder, postorder, level-order. Each in $O(n)$.
BST: ordering invariant; search / insert / delete in $O(h)$.
Binary heap (min/max): complete tree; $O(\log n)$ operations; heapsort in $O(n \log n)$.
Balanced BSTs (AVL, red-black) guarantee $O(\log n)$ worst-case.
Bridging: convert binary tree → graph dict; reuse BFS/DFS/diameter algorithms.

18 / 21

31. Python toolbox — quick reference

Python — what to import for graph & tree work from collections import deque # BFS queue import heapq # Dijkstra, Prim, heaps import functools # reduce, lru_cache # Adjacency-list graph G = {'a': {'b': 3, 'c': 1}, 'b': {'a': 3, 'c': 7}, 'c': {'a': 1, 'b': 7}} # Binary tree T = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]] # Optional: NetworkX for sanity checks (a library, not for the from-scratch exercises) # import networkx as nx # nx_G = nx.Graph() # nx_G.add_weighted_edges_from([(u, v, w) for u in G for v, w in G[u].items() if u < v]) # nx.shortest_path(nx_G, 'a', 'b', weight='weight')

In exercises and assessments, do not rely on NetworkX — students are expected to implement BFS, DFS, Dijkstra, Kruskal/Prim, and tree operations from scratch using the standard dict and list representations. NetworkX is a convenient sanity check, not a substitute for the explicit implementations.

19 / 21

Bibliography

K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §§10.1–10.7 (graphs), §§11.1–11.5 (trees).
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, 4th ed., MIT Press, 2022 — Part VI (graph algorithms), ch. 12–13 (BST, balanced trees), ch. 6 (heaps).
D. Beauquier, J. Berstel, P. Chrétienne. Éléments d'algorithmique, Masson, 1992 — standard French-language algorithmics reference.
R. Diestel. Graph Theory, 5th ed., Springer, 2017 — standard mathematical reference.
D. E. Knuth. The Art of Computer Programming, vol. 1 (Fundamental Algorithms), vol. 3 (Sorting and Searching), Addison-Wesley.
H. Abelson & G. J. Sussman. Structure and Interpretation of Computer Programs, 2nd ed., MIT Press, 1996 — §2.2 (tree-like data).
L. Euler (1736). Solutio problematis ad geometriam situs pertinentis — origins of graph theory.
K. Appel & W. Haken (1976). Four-color theorem.
E. W. Dijkstra (1959). A note on two problems in connexion with graphs, Numer. Math. 1.
S. S. Skiena. The Algorithm Design Manual, 3rd ed., Springer, 2020 — graphs and trees from the algorithms-engineering perspective.

Notes By Pr. El Hadiq Zouhair

20 / 21

End of course

Thank you

Questions, exercises and lab sessions to follow.

Notes By Pr. El Hadiq Zouhair

21 / 21