Trees and Graphs: Binary Trees, BST, AVL, Traversals, BFS, DFS and MST

Tree terminology

A tree is a non-linear, hierarchical structure of nodes connected by edges, with one root and no cycles.

• Parent, child, sibling: related nodes.
• Leaf: a node with no children.
• Degree: the number of children of a node.
• Level / depth: the root is at level 0.
• Height: the length of the longest path from the root to a leaf.

Binary tree

Each node has at most two children (left and right).

• Full (strict) binary tree: every node has 0 or 2 children.
• Complete binary tree: every level is full except possibly the last, which is filled from the left.
• A binary tree of height h has at most 2^(h+1) − 1 nodes.

Traversals

For the tree:

        A
       / \
      B   C
     / \   \
    D   E   F

• Preorder (Root, Left, Right): A B D E C F
• Inorder (Left, Root, Right): D B E A C F
• Postorder (Left, Right, Root): D E B F C A
• Level order (BFS): A B C D E F

void inorder(struct tnode *t) {
    if (t) { inorder(t->left); printf("%d ", t->data); inorder(t->right); }
}

Binary search tree (BST)

For every node: all keys in the left subtree are smaller, and all keys in the right subtree are larger. Inorder traversal gives the keys in sorted order.

• Search / insert: start at the root and go left or right by comparison. O(h).
• Delete:
  • a leaf: just remove it;
  • one child: replace the node with its child;
  • two children: replace its value with its inorder successor (the smallest key in the right subtree), then delete that successor.

Example: inserting 50, 30, 70, 20, 40, 60, 80 builds a balanced tree of height 2. Inserting 10, 20, 30, 40 in that order builds a skewed tree (like a linked list), and searches become O(n).

AVL tree

A self-balancing BST in which, for every node, the balance factor = height(left) − height(right) ∈ {−1, 0, +1}. After an insertion or deletion, restore the balance with a rotation:

• LL case: the new node is in the left subtree of the left child: single right rotation.
• RR case: the new node is in the right subtree of the right child: single left rotation.
• LR case: left child's right subtree: left rotation on the child, then right rotation.
• RL case: right child's left subtree: right rotation on the child, then left rotation.

Height stays O(log n), so every operation is O(log n).

Heap

A complete binary tree stored in an array, where each parent is ≥ its children (max-heap) or ≤ them (min-heap). For the node at index i (1-based), the children are at 2i and 2i + 1. Heaps are used for priority queues and heap sort.

Graphs

A graph G = (V, E) is a set of vertices and edges. It can be directed or undirected, and weighted or unweighted.

Representation

• Adjacency matrix: a V × V matrix; A[i][j] = 1 (or the weight) if there is an edge. O(V²) space; checking an edge is O(1).
• Adjacency list: each vertex keeps a list of its neighbours. O(V + E) space; good for sparse graphs.

Breadth-first search (BFS)

Uses a queue: visit the start vertex, then all its neighbours, then their unvisited neighbours, level by level. O(V + E). It finds the shortest path (fewest edges) in an unweighted graph.

Depth-first search (DFS)

Uses a stack (or recursion): go as deep as possible along one path, then backtrack. O(V + E). It is used for cycle detection, topological sort and connected components.

Minimum spanning tree (MST)

A spanning tree that connects all vertices with the minimum total edge weight (for a connected, weighted, undirected graph).

• Kruskal's algorithm: sort the edges by weight; add the next smallest edge if it does not form a cycle (checked with union-find). O(E log E).
• Prim's algorithm: start from any vertex and repeatedly add the cheapest edge that connects the tree to a new vertex. O(E log V) with a heap.

Shortest path: Dijkstra's algorithm

This finds the shortest paths from one source to all vertices when all edge weights are non-negative.

1. Set dist[source] = 0 and every other dist = ∞.
2. Repeatedly pick the unvisited vertex u with the smallest dist, and mark it visited.
3. For each neighbour v of u: if dist[u] + w(u, v) < dist[v], update dist[v].

O((V + E) log V) with a min-heap.

Exam tip

Tree traversals, BST/AVL construction and "apply Kruskal or Prim to this graph" are the most-repeated questions in this unit. Show the tree after every insertion or rotation, and list the edges in the order they were chosen for an MST.