1. Trees

Definition – Tree

A tree is a non-linear structure of nodes where each node has a single predecessor (parent) but can have many successors (children).

flowchart TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))
    C --> H((H))
    H --> I((I))

Terminology

TermDefinitionIn the example
Rootnode with no parentA
Parent / childdirect predecessor / successorB is parent of D, E; I is child of H
Leafnode with no childrenD, E, F, G, I
Internal nodenode with childrenA, B, C, H
Ancestor / descendant is an ancestor of if there’s a path from to A is an ancestor of I
Pathsequence of nodes passed through from to A–B–D
Path lengthnumber of arcs = number of nodes − 1A→D has length 2
Depth of length of the path root → depth(F) = 2
Height of length of the longest path → leafheight(C) = 2
Height of treeheight of its root3
Level all nodes of depth level 1 = {B, C}
Sizetotal number of nodes9
Degree of a nodenumber of its childrendeg(C) = 3
Degree of a treemaximum node degree3

Recursive definitions:

Worked example – heights (bottom-up)

  • (leaf) →
  • →
  • →
  • = height of the tree.

2. Binary Trees

Definition – Binary tree

A tree of degree 2: each node has at most a left child and a right child.

Properties

  • Maximum number of nodes at level : .
  • Maximum size of a binary tree of height : .

Worked example: height → at most nodes ().

⚠️ The slide writes "" but the formula also holds for (one node: ).

Full vs complete binary trees

TypeDefinition
Fullevery node is either a leaf or has exactly two non-empty children
Completeif the height is , all levels except possibly level are completely full, and the bottom level has its nodes packed to the left
flowchart TD
    subgraph Full ["(a) Full"]
    a1((·)) --> a2((·))
    a1 --> a3((·))
    a2 --> a4((·))
    a2 --> a5((·))
    a5 --> a6((·))
    a5 --> a7((·))
    end
    subgraph Complete ["(b) Complete"]
    b1((·)) --> b2((·))
    b1 --> b3((·))
    b2 --> b4((·))
    b2 --> b5((·))
    b3 --> b6((·))
    b4 --> b7((·))
    end

⚠️ Full ≠ complete: a full tree can be very unbalanced, and a complete tree can have a node with one child (the last internal node).

Theorem – Full binary tree

In a non-empty full binary tree, the number of leaves is one more than the number of internal nodes: internal leaves .

Worked example: tree (a) above has internal nodes {root, left child, its right child} = 3 and leaves = 4 ✓.


3. Implementation by Pointers

Each node keeps a pointer to its left child and one to its right child; a missing child → NULL.

template <class Element>
class BTree {
    class BNode {
    public:
        BNode *left;  Element data;  BNode *right;
        BNode(const Element &d) { left = 0; data = d; right = 0; }
        bool isLeaf() { return left == NULL && right == NULL; }
    };
    BNode *root;
public:
    BTree() { root = NULL; }
    bool isEmpty() const;
    void insert(const Element &d);
    void remove(const Element &d);
    void print() const;
};

4. Space Overhead

Let = size of a pointer, = size of the data. Each node uses , so a tree of nodes uses , of which is structure (pointers).

If leaves (≈ half the nodes in a full tree) store no pointers:


5. Binary Tree Traversals

Definition – Traversals

TraversalOrder
Inorderleft subtree (inorder) → root → right subtree (inorder)
Preorderroot → left subtree (preorder) → right subtree (preorder)
Postorderleft subtree (postorder) → right subtree (postorder) → root
void Inorder(BNode *r)   { if (r) { Inorder(r->left);   Visit(r); Inorder(r->right); } }
void Preorder(BNode *r)  { if (r) { Visit(r); Preorder(r->left);  Preorder(r->right); } }
void Postorder(BNode *r) { if (r) { Postorder(r->left); Postorder(r->right); Visit(r); } }

Called from the root; recursion visits every subtree.

Worked example

flowchart TD
    R((R)) --> A((A))
    R --> D((D))
    A --> B((B))
    A --> C((C))
    D --> X[ ]
    D --> E((E))
    style X fill:none,stroke:none
TraversalResult
InorderB – A – C – R – D – E
PreorderR – A – B – C – D – E
PostorderB – C – A – E – D – R

6. Implementation by Array

Since the degree is 2, cells can be reserved in advance in a sequential array: node 0 at index 0, its children at 1 and 2, etc. (root at 0 → children of at and ).

Worked example

flowchart TD
    O((O)) --> M((M))
    O --> T((T))
    M --> C((C))
    M --> E((E))
    T --> P((P))
    T --> U((U))
0123456
OMTCEPU

⚠️ If the tree is not complete, the array has empty cells (wasted space). This is why arrays suit complete trees, e.g. heaps.


7. Priority Queues

Definition – Priority queue

Stores objects and, on request, releases the object with the greatest value (highest priority).

  • Example: scheduling jobs in a multitasking OS; a job’s priority may change → reordering.
  • Implementation: a heap.

8. Heaps

Definition – Heap

A complete binary tree with the heap property:

  • Min-heap: every value is less than its children’s values;
  • Max-heap: every value is greater than its children’s values.

Values are only partially ordered (no order between siblings). Usually stored as an array.

Array representation (root at index 1)

For a node at position in a heap of size :

ElementPosition
Root1
Left child
Right child
Father
Is a leaf
Has 2 children
Has 1 child
Last internal node

Worked example – heap T = [_, 13, 21, 16, 24, 31, 19, 68, 65, 26, 32] ()

flowchart TD
    n13((13)) --> n21((21))
    n13 --> n16((16))
    n21 --> n24((24))
    n21 --> n31((31))
    n16 --> n19((19))
    n16 --> n68((68))
    n24 --> n65((65))
    n24 --> n26((26))
    n31 --> n32((32))
  • Node 24 is at : father , children , .
  • Node 31 at : → exactly one child ().
  • Last internal node: ; positions 6–10 are leaves.
template <class Elem> class minHeap {
    Elem *tab; int max; int n;
    void putHeap();
public:
    int  Parent(int pos)     const { return (pos > 1 && pos <= n) ? pos / 2 : -1; }
    int  leftChild(int pos)  const { return 2 * pos; }
    int  rightChild(int pos) const { return 2 * pos + 1; }
    bool isLeaf(int pos)     const { return pos > n / 2 && pos <= n; }
    void insert(const Elem val);
    Elem deleteMin();
};

9. Insertion in a Heap (sift-up)

Algorithm

  1. Increment and put the new value at (end of the array).
  2. While the value is smaller than its father (min-heap), swap with the father and move up.
template <class Elem>
void minHeap<Elem>::insert(const Elem val) {
    if (n < max) {
        int current = ++n;
        tab[current] = val;
        while (current > 1 && tab[current] < tab[Parent(current)]) {
            swap(tab[current], tab[Parent(current)]);
            current = Parent(current);
        }
    }
}

Worked example – insert 14

StepPosition of 14FatherActionArray (1..11)
11114 < 31 → swap13 21 16 24 14 19 68 65 26 32 31
2514 < 21 → swap13 14 16 24 21 19 68 65 26 32 31
3214 > 13 → stop13 14 16 24 21 19 68 65 26 32 31
flowchart TD
    n13((13)) --> n14((14))
    n13 --> n16((16))
    n14 --> n24((24))
    n14 --> n21((21))
    n16 --> n19((19))
    n16 --> n68((68))
    n24 --> n65((65))
    n24 --> n26((26))
    n21 --> n32((32))
    n21 --> n31((31))
    style n14 fill:#fde68a,stroke:#b45309,color:#2a1f33

10. Deletion in a Heap (deleteMin, sift-down)

Algorithm

  1. Remove the root (the minimum).
  2. Move the rightmost node of the last level (i.e. ) to the root; decreases.
  3. Compare it with its children; if it is greater than one of them, swap with the smaller child.
  4. Repeat until the heap property holds.
template <class Elem>
Elem minHeap<Elem>::deleteMin() {
    if (n == 0) return NULL;          // empty heap
    Elem temp = tab[1];
    tab[1] = tab[n--];                // last element to the root
    if (n > 1) putHeap();
    return temp;
}
 
template <class Elem>
void minHeap<Elem>::putHeap() {
    int pos = 1;
    while (!isLeaf(pos)) {
        int l = leftChild(pos), r = rightChild(pos);
        if (r <= n && tab[r] < tab[l]) l = r;   // l = smaller child
        if (tab[pos] <= tab[l]) return;
        swap(tab[pos], tab[l]);
        pos = l;
    }
}

Worked example – delete the root 2 from [2, 3, 4, 7, 5, 6]

StepArrayAction
02 3 4 7 5 6remove 2
16 3 4 7 5last element 6 → root
23 6 4 7 5children 3, 4 → smaller is 3 → swap
33 5 4 7 6children 7, 5 → smaller is 5 → swap; 6 is now a leaf → stop
flowchart TD
    a3((3)) --> a5((5))
    a3 --> a4((4))
    a5 --> a7((7))
    a5 --> a6((6))

⚠️ Always swap with the smaller child (min-heap) — swapping with the larger one breaks the heap property. Also, return NULL only compiles for pointer/numeric Elem; and in the slide pos is used without being declared (int pos = 1;). “minTas” in the slides is the French name for minHeap.


11. Complexity of Heap Operations

A complete binary tree of nodes has height , and insertion/deletion never do more swaps than the height.

OperationComplexity
Insert
Delete min (max)
Find min in a min-heap (max in a max-heap)