Lesson 10 — Trees vs Graphs & Advanced Topics

📖

Trees vs Graphs — The Direct Comparison

Here's the fact that ties both lessons together: every tree is a graph, but not every graph is a tree. A tree is simply a graph with extra restrictions — no cycles, exactly one root, and exactly N−1 edges for N nodes.

Property	Tree	Graph
Cycles	Never allowed	Allowed (unless explicitly acyclic / DAG)
Root	Exactly one	No concept of a root (unless rooted explicitly)
Edges for N nodes	Always exactly N−1	Any number, from 0 to N×(N−1)
Parent-child	Every non-root has exactly 1 parent	A vertex can have many "parents" (in-edges)
Connectivity	Always fully connected	May be disconnected (multiple components)
Typical storage	Node struct with left/right or children[]	Adjacency matrix or adjacency list
Typical traversal	Inorder / Preorder / Postorder (DFS variants)	BFS / DFS with a visited[] array
Real-world examples	File systems, DOM, org charts, BSTs	Road maps, social networks, the web, flight routes

💡 Why trees don't need visited[]. Since a tree has no cycles and exactly one path between any two nodes, recursive traversal can never loop forever. Graphs can have cycles, so every graph traversal (BFS/DFS) must track a visited[] array — otherwise it can revisit the same vertices infinitely.

1

Weighted Graphs & Dijkstra's Shortest Path

Greedy + adjacency matrix

BFS finds the shortest path only when every edge has the same "cost." Real roads have distances, real networks have latency. Dijkstra's algorithm finds the shortest path in a weighted graph by always expanding the closest unvisited vertex next.

(2) (1) 0 ------ 1 ------ 3 \ / (4) \ / (7) \ / --- 2 --- Shortest 0→3 = 0-1-3 = 2+1 = 3 (not 0-2-3 = 4+7 = 11)

Example 1 · dijkstra.c

dijkstra.c

C

#include <stdio.h>
#define V 4
#define INF 9999

int minDistance(int dist[], int visited[]) {
    int min = INF, minIndex = -1;
    for (int v = 0; v < V; v++)
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    return minIndex;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int visited[V] = {0};

    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);   // closest unvisited vertex
        visited[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] &&
                dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];   // relax the edge
            }
        }
    }

    printf("Vertex   Distance from %d\n", src);
    for (int i = 0; i < V; i++)
        printf("%d        %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 2, 4, 0},
        {2, 0, 0, 1},
        {4, 0, 0, 7},
        {0, 1, 7, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

terminal

output

Vertex   Distance from 0
0        0
1        2
2        4
3        3

💡 "Relaxing an edge" means: if going through u gives a shorter path to v than what we currently know, update it. Dijkstra repeats this for every vertex, always picking the nearest unvisited one next — a greedy strategy that works because edge weights are non-negative.

2

Topological Sort

DFS on a DAG

A Directed Acyclic Graph (DAG) models tasks with dependencies — like course prerequisites. Topological sort orders the vertices so every edge u → v has u appearing before v. It's built on DFS, using a stack to reverse finishing order.

5 -> 0 4 -> 0 5 -> 2 2 -> 3 3 -> 1 4 -> 1 Valid order: 5 4 2 3 1 0 (prerequisites always come first)

Example 2 · topological_sort.c

topological_sort.c

C

#include <stdio.h>
#define V 6

int graph[V][V] = {
    {0,0,0,0,0,0},
    {0,0,0,0,0,0},
    {0,0,0,1,0,0},
    {0,1,0,0,0,0},
    {1,1,0,0,0,0},
    {1,0,1,0,0,0}
};
int visited[V] = {0};
int stack[V], top = -1;

void dfs(int v) {
    visited[v] = 1;
    for (int i = 0; i < V; i++)
        if (graph[v][i] && !visited[i])
            dfs(i);
    stack[++top] = v;   // push v only after all its dependents are done
}

int main() {
    for (int i = 0; i < V; i++)
        if (!visited[i])
            dfs(i);

    printf("Topological order: ");
    while (top >= 0)
        printf("%d ", stack[top--]);
    printf("\n");
    return 0;
}

terminal

output

Topological order: 5 4 2 3 1 0

⚠️ Only works on a DAG. If the graph has a cycle, there is no valid ordering — task A can't come before B if B also has to come before A. Always confirm the graph is acyclic before sorting.

3

Checking If a Binary Tree Is Balanced

Recursive height comparison

The BST lesson warned that a skewed tree degrades to O(n). A tree is height-balanced if, for every node, the heights of its left and right subtrees differ by no more than 1. This check is what self-balancing trees (AVL) use after every insert.

Example 3 · is_balanced.c

is_balanced.c

C

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* newNode(int val) {
    Node *n = malloc(sizeof(Node));
    n->data = val;
    n->left = n->right = NULL;
    return n;
}

// returns height, or -1 up the call stack the moment it's unbalanced
int checkHeight(Node *root) {
    if (root == NULL) return 0;

    int lh = checkHeight(root->left);
    if (lh == -1) return -1;    // left already unbalanced

    int rh = checkHeight(root->right);
    if (rh == -1) return -1;    // right already unbalanced

    if (abs(lh - rh) > 1) return -1;  // this node breaks balance

    return 1 + (lh > rh ? lh : rh);
}

int isBalanced(Node *root) {
    return checkHeight(root) != -1;
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);

    printf("Balanced? %s\n", isBalanced(root) ? "YES" : "NO");

    root->left->left->left = newNode(5);   // pushes left subtree deeper
    printf("Balanced? %s\n", isBalanced(root) ? "YES" : "NO");

    return 0;
}

terminal

output

Balanced? YES
Balanced? NO

💡 Returning -1 as a sentinel lets one pass do double duty: it computes height AND detects imbalance, stopping recursion early instead of computing height everywhere then comparing separately (which would be O(n²) on a skewed tree).

4

Diameter & Mirror of a Binary Tree

Two classic tree problems

The diameter is the longest path between any two nodes — it may or may not pass through the root. Mirroring a tree swaps every left and right child, flipping the whole shape like a reflection.

Example 4 · diameter_mirror.c

diameter_mirror.c

C

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* newNode(int val) {
    Node *n = malloc(sizeof(Node));
    n->data = val; n->left = n->right = NULL;
    return n;
}

int diameter = 0;

// height() also updates the global diameter as a side effect
int height(Node *root) {
    if (!root) return 0;
    int lh = height(root->left);
    int rh = height(root->right);

    if (lh + rh > diameter) diameter = lh + rh;  // path through this node

    return 1 + (lh > rh ? lh : rh);
}

void mirror(Node *root) {
    if (!root) return;
    Node *temp = root->left;
    root->left = root->right;
    root->right = temp;
    mirror(root->left);
    mirror(root->right);
}

void inorder(Node *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    height(root);   // fills in `diameter` as a side effect
    printf("Diameter: %d\n", diameter);

    printf("Inorder before mirror: "); inorder(root); printf("\n");
    mirror(root);
    printf("Inorder after mirror : "); inorder(root); printf("\n");

    return 0;
}

terminal

output

Diameter: 3
Inorder before mirror: 4 2 5 1 3
Inorder after mirror : 3 1 5 2 4

Problem	Technique	Time
Dijkstra	Greedy + relax edges	O(V²) with a matrix
Topological sort	DFS + stack on finish order	O(V+E)
Balanced check	Height with -1 sentinel	O(n)
Diameter	Height with global side effect	O(n)
Mirror	Swap children, recurse	O(n)

Q

Quick Quiz

Question 1 of 5

Which statement is always true?

Question 2 of 5

Why does Dijkstra's algorithm beat plain BFS on a weighted graph?

Question 3 of 5

Topological sort is only valid on which kind of graph?

Question 4 of 5

In the balanced-tree check, why return -1 as a sentinel?

Question 5 of 5

Why don't tree traversals need a visited[] array, unlike graph traversals?

✓

Lesson Checklist

I can explain why every tree is a graph, but not vice versa
I know why trees don't need a visited[] array but graphs do
I understand Dijkstra's "relax the edge" idea
I can trace Dijkstra on a small weighted graph
I understand what a DAG is and why cycles break topological sort
I can implement topological sort using DFS + a stack
I can check if a binary tree is height-balanced
I can compute the diameter of a binary tree
I can mirror/invert a binary tree
I completed the quiz

Trees vs Graphs - Comparison

Trees vs Graphs — The Direct Comparison

Weighted Graphs & Dijkstra's Shortest Path

Topological Sort

Checking If a Binary Tree Is Balanced

Diameter & Mirror of a Binary Tree

Quick Quiz

Lesson Checklist