Terminology

The root has no parent. Children belong below a parent; siblings share a parent. A leaf has no children. A node’s degree is its number of children. A subtree contains a selected node and its descendants. This material measures height in edges: a leaf has height 0.

Types

1. A binary tree has at most two ordered children per node.
2. A full or strict binary tree gives every node either zero or two children.
3. A complete binary tree fills every level except possibly the last, which is filled from left to right.
4. A perfect binary tree has all internal nodes with two children and all leaves at one level.
5. A skewed binary tree forms a one-sided chain.

Examples

A root with two leaf children is perfect, full and complete. A chain is still a binary tree but can have height n - 1. A binary tree is not automatically a binary search tree: the search-order rule must be separately maintained.

Counting and cost

A non-empty finite tree with n nodes has n - 1 parent-child edges. Traversing every node is O(n). Algorithms following a root-to-leaf path depend on height h, so the shape affects their work and recursive call depth.

Important convention

Some texts count height in nodes rather than edges. State the convention before using a numerical formula instead of treating two consistent conventions as contradictory.

Diagram or flowchart

Conversion

1. Preserve a chosen order among each node’s children.
2. Use the left pointer for the first child.
3. Connect that child’s right pointer to the next sibling, continuing across the sibling group.
4. Represent missing first children or next siblings with NULL.

Example

Suppose A has children B, C and D, and B has child E. Set A.left = B, B.right = C and C.right = D. Set B.left = E. D.right is NULL. The original root has no next sibling, so A.right is NULL.

Interpretation

C is a sibling of B, not an original child of B. Reading both links as original parent-child relations would misinterpret the general tree. The transformed pointer arrangement is binary in representation, but its semantic link meanings must remain clear.

Advantages

A node needs two links regardless of how many children it has. There is no fixed child-array capacity to choose for every node. Iterating a node’s children means following the first-child link and then the sibling chain.

Complexity

Creating one representation node per original node and linking each relationship once takes O(n) structural work and O(n) representation storage. Traversing a node’s k children via siblings takes O(k). This conversion is not a numeric BST insertion or balancing operation.

Diagram or flowchart

Recursive algorithms

1. Preorder: if node exists, visit it, traverse left, traverse right.
2. Inorder: traverse left, visit the node, traverse right.
3. Postorder: traverse left, traverse right, visit the node.
4. For a NULL subtree, return without visiting.

Worked example

For root 1, children 2 and 3, and children 4 and 5 under node 2: preorder is 1 2 4 5 3; inorder is 4 2 5 1 3; postorder is 4 5 2 3 1. The complete example prints these orders.

Iterative alternative

For inorder without recursion, use an explicit node-pointer stack. Push nodes while moving left. When no left node remains, pop and visit one, then move to its right subtree. Repeat while either the current node exists or the stack is non-empty. The stack replaces the pending recursive calls.

Applications

Preorder can describe a parent before descendants. Postorder is useful when children must be handled before a parent, including tree destruction. Inorder gives increasing keys for a BST with its stated ordering policy, but not for every arbitrary binary tree.

Complexity

Each node is visited once, so time is O(n). Recursive call depth is O(h), where h is tree height; it becomes O(n) for a chain. An explicit traversal stack has the corresponding height-dependent storage. A NULL root produces no values.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
struct Node { int key; struct Node *left, *right; };
void preorder(const struct Node *p) { if (p != NULL) { printf("%d ", p->key); preorder(p->left); preorder(p->right); } }
void inorder(const struct Node *p) { if (p != NULL) { inorder(p->left); printf("%d ", p->key); inorder(p->right); } }
void postorder(const struct Node *p) { if (p != NULL) { postorder(p->left); postorder(p->right); printf("%d ", p->key); } }

int main(void)
{
    struct Node n4 = {4, NULL, NULL}, n5 = {5, NULL, NULL};
    struct Node n2 = {2, &n4, &n5}, n3 = {3, NULL, NULL}, root = {1, &n2, &n3};
    printf("Preorder: "); preorder(&root); putchar('\n');
    printf("Inorder: "); inorder(&root); putchar('\n');
    printf("Postorder: "); postorder(&root); putchar('\n');
    return 0;
}

Preorder: 1 2 4 5 3 
Inorder: 4 2 5 1 3 
Postorder: 4 5 2 3 1

ADT operations

A BST interface can create an empty tree, search a key, insert a new key, remove a key and traverse or destroy the tree. The interface should define duplicate handling and how absence or allocation failure is reported.

Search algorithm

1. Start at root.
2. If the current node is NULL, report not found.
3. If key equals its key, report found.
4. If key is smaller, move left; otherwise move right.

Example

For root 50, left child 30 and right child 70, searching 40 first moves left. If 30 has right child 40, the next move reaches it. The comparisons exclude the opposite subtree because all its keys lie on the wrong side of the BST ordering rule.

Shape and duplicates

Inserting sorted keys into an ordinary unbalanced BST can make a chain. A basic BST does not automatically maintain a logarithmic height. Other duplicate policies can be valid, but must be consistent with searching, insertion and deletion.

Complexity

A search follows at most one root-to-leaf path, so it takes O(h) time. A reasonably balanced shape has h = O(log n); worst-case height is O(n). An iterative search needs O(1) auxiliary space. Inorder traversal visits all n keys in sorted order under the stated policy.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int key; struct Node *left, *right; };
struct Node *insert(struct Node *root, int key, int *ok)
{
    if (root == NULL) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) { *ok = 0; return NULL; }
        node->key = key; node->left = node->right = NULL; return node;
    }
    if (key < root->key) { root->left = insert(root->left, key, ok); }
    else if (key > root->key) { root->right = insert(root->right, key, ok); }
    return root;
}
const struct Node *search(const struct Node *root, int key)
{
    while (root != NULL && root->key != key) { root = key < root->key ? root->left : root->right; }
    return root;
}
struct Node *remove_key(struct Node *root, int key)
{
    if (root == NULL) { return NULL; }
    if (key < root->key) { root->left = remove_key(root->left, key); }
    else if (key > root->key) { root->right = remove_key(root->right, key); }
    else {
        if (root->left == NULL) { struct Node *next = root->right; free(root); return next; }
        if (root->right == NULL) { struct Node *next = root->left; free(root); return next; }
        struct Node *successor = root->right;
        while (successor->left != NULL) { successor = successor->left; }
        root->key = successor->key;
        root->right = remove_key(root->right, successor->key);
    }
    return root;
}
void inorder(const struct Node *root)
{
    if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); }
}
void destroy(struct Node *root)
{
    if (root != NULL) { destroy(root->left); destroy(root->right); free(root); }
}

int main(void)
{
    struct Node *root = NULL; int ok = 1;
    int keys[7] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); puts("Allocation failed"); return 1; }
    }
    printf("Search 40: %s\n", search(root, 40) != NULL ? "Found" : "Not found");
    root = remove_key(root, 20); root = remove_key(root, 30); root = remove_key(root, 50);
    inorder(root); putchar('\n'); destroy(root); root = NULL;
    return 0;
}

Search 40: Found
40 60 70 80

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q6(a) · 5 marks

  Illustrate search in a binary search tree.

  Paper DS01 · page 1
• February 2024 · Q1(e) · 1 marks

  Define a binary search tree.

  Paper DS03 · page 1
• March 2021 · Q3(b) · 8 marks

  Explain binary search trees.

  Paper DS04 · page 1

View all matching source questions →

Algorithm

1. If root is NULL, allocate and initialise a new root node.
2. Otherwise compare the new key at each visited node.
3. Move left for a smaller key and right for a larger key.
4. At a NULL child link, attach a checked new node.
5. For an equal key, follow the chosen duplicate policy; this example leaves the tree unchanged.

Example

Insert 50, 30, 70, 20 and 40. The first key becomes root. 30 goes left of 50 and 70 right. 20 goes left of 30; 40 goes right of 30. Inorder traversal is 20, 30, 40, 50, 70.

Memory handling

Set a new node’s child links to NULL. If allocation fails, leave the existing tree valid and report failure. A recursive implementation must return the possibly changed subtree root and the caller must store it, including the first insertion into an empty tree.

Order matters

The same key set can form different shapes for different insertion orders. The values are ordered logically by comparisons, not necessarily by the physical addresses of the nodes. This operation does not perform AVL or red-black balancing.

Complexity

Insertion follows one path of height h, giving O(h) comparisons plus node allocation. Worst case is O(n); a balanced shape gives O(log n). Recursive extra call space is O(h), while an iterative implementation can keep fixed working pointers.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int key; struct Node *left, *right; };
struct Node *insert(struct Node *root, int key, int *ok)
{
    if (root == NULL) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) { *ok = 0; return NULL; }
        node->key = key; node->left = node->right = NULL; return node;
    }
    if (key < root->key) { root->left = insert(root->left, key, ok); }
    else if (key > root->key) { root->right = insert(root->right, key, ok); }
    return root;
}
const struct Node *search(const struct Node *root, int key)
{
    while (root != NULL && root->key != key) { root = key < root->key ? root->left : root->right; }
    return root;
}
struct Node *remove_key(struct Node *root, int key)
{
    if (root == NULL) { return NULL; }
    if (key < root->key) { root->left = remove_key(root->left, key); }
    else if (key > root->key) { root->right = remove_key(root->right, key); }
    else {
        if (root->left == NULL) { struct Node *next = root->right; free(root); return next; }
        if (root->right == NULL) { struct Node *next = root->left; free(root); return next; }
        struct Node *successor = root->right;
        while (successor->left != NULL) { successor = successor->left; }
        root->key = successor->key;
        root->right = remove_key(root->right, successor->key);
    }
    return root;
}
void inorder(const struct Node *root)
{
    if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); }
}
void destroy(struct Node *root)
{
    if (root != NULL) { destroy(root->left); destroy(root->right); free(root); }
}

int main(void)
{
    struct Node *root = NULL; int ok = 1;
    int keys[7] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); puts("Allocation failed"); return 1; }
    }
    printf("Search 40: %s\n", search(root, 40) != NULL ? "Found" : "Not found");
    root = remove_key(root, 20); root = remove_key(root, 30); root = remove_key(root, 50);
    inorder(root); putchar('\n'); destroy(root); root = NULL;
    return 0;
}

Search 40: Found
40 60 70 80

Algorithm

1. Search recursively or iteratively for the key. A missing key leaves the tree unchanged.
2. For a leaf, free it and replace its parent link with NULL.
3. For one child, replace the target link with its child, then free the target.
4. For two children, find the minimum node in the right subtree, copy its key or full associated record as appropriate, and delete that successor from the right subtree.

Why the successor works

The right-subtree minimum is greater than every key in the left subtree and no larger than the remaining right-subtree keys. It has no left child, so deleting its old node reduces to a simpler case. Do not copy a whole node object including its link pointers as though that were only a key replacement.

Example

The demonstration builds 50, 30, 70, 20, 40, 60, 80. It deletes 20 as a leaf, 30 as a one-child node and 50 as a two-child root. The final inorder sequence is 40, 60, 70, 80.

Boundary cases

Deleting the root can change the root pointer. Removing the only node makes the tree empty. Free exactly the removed node and keep no usable alias to it. A missing-key deletion is a normal unsuccessful operation.

Complexity

Search and successor location follow paths bounded by tree height, giving O(h) time. Worst case is O(n), not unconditionally logarithmic. Recursive deletion uses O(h) call space. Destroy all remaining owned nodes when finished.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int key; struct Node *left, *right; };
struct Node *insert(struct Node *root, int key, int *ok)
{
    if (root == NULL) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) { *ok = 0; return NULL; }
        node->key = key; node->left = node->right = NULL; return node;
    }
    if (key < root->key) { root->left = insert(root->left, key, ok); }
    else if (key > root->key) { root->right = insert(root->right, key, ok); }
    return root;
}
const struct Node *search(const struct Node *root, int key)
{
    while (root != NULL && root->key != key) { root = key < root->key ? root->left : root->right; }
    return root;
}
struct Node *remove_key(struct Node *root, int key)
{
    if (root == NULL) { return NULL; }
    if (key < root->key) { root->left = remove_key(root->left, key); }
    else if (key > root->key) { root->right = remove_key(root->right, key); }
    else {
        if (root->left == NULL) { struct Node *next = root->right; free(root); return next; }
        if (root->right == NULL) { struct Node *next = root->left; free(root); return next; }
        struct Node *successor = root->right;
        while (successor->left != NULL) { successor = successor->left; }
        root->key = successor->key;
        root->right = remove_key(root->right, successor->key);
    }
    return root;
}
void inorder(const struct Node *root)
{
    if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); }
}
void destroy(struct Node *root)
{
    if (root != NULL) { destroy(root->left); destroy(root->right); free(root); }
}

int main(void)
{
    struct Node *root = NULL; int ok = 1;
    int keys[7] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); puts("Allocation failed"); return 1; }
    }
    printf("Search 40: %s\n", search(root, 40) != NULL ? "Found" : "Not found");
    root = remove_key(root, 20); root = remove_key(root, 30); root = remove_key(root, 50);
    inorder(root); putchar('\n'); destroy(root); root = NULL;
    return 0;
}

Search 40: Found
40 60 70 80

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q6(a) · 5 marks

  Give BST deletion algorithm with an example.

  Paper DS03 · page 2
• October 2020 · Q8 · 15 marks

  Give BST deletion algorithm.

  Paper DS06 · page 1

View all matching source questions →

Types

1. An undirected edge connects both endpoints without direction.
2. A directed edge has a source and destination.
3. A weighted graph assigns an edge value such as cost or distance.
4. A simple graph excludes parallel edges and loops under the usual convention.
5. A connected undirected graph has a path between every pair; a directed graph needs more precise reachability terminology.

Terminology

Adjacent vertices share a suitable edge. A path follows successive edges. A cycle returns to its starting vertex through the stated path convention. In an undirected graph, degree counts incident edges with loops treated by the chosen convention. A directed graph separates in-degree and out-degree.

Example

Cities can be vertices and flights directed edges. A flight from city 2 to city 3 does not imply a return flight unless a separate edge is supplied. If time or price matters, store it as a weight with a defined meaning.

Tree relationship

A finite connected undirected acyclic graph is a tree. A graph in general can contain cycles and disconnected components. Traversal therefore needs a visited record; merely following neighbours without one can revisit vertices indefinitely.

Storage and operations

The representation controls adjacency tests and neighbour enumeration. An adjacency matrix uses O(V²) space, while adjacency lists use O(V + E) space for the usual representation. The ADT should specify edge direction, duplicate-edge and weight rules.

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q1(h) · 1 marks

  Define a graph.

  Paper DS03 · page 1

View all matching source questions →

Matrix

A V-by-V array allows a direct O(1) edge test for valid indices. It uses O(V²) storage even for a sparse graph. Listing one vertex’s neighbours scans its row and can require O(V) work. A weighted representation needs a clear absent-edge encoding that does not confuse a valid zero weight with absence.

List

Each vertex stores its adjacent vertices or outgoing edges. Space is O(V + E), with an undirected edge ordinarily represented at both endpoints. Enumerating neighbours takes work proportional to the stored degree. A basic unsorted-list edge lookup can require O(degree) comparisons.

Example

For undirected edges 0–1, 0–2, 1–3 and 2–4, row 0 has ones at columns 1 and 2. The list for 0 is [1, 2]. The list for 1 includes 0 and 3. Directed edges would not automatically create these reverse entries.

Choosing

Use a matrix when graphs are small or dense and frequent edge tests matter. Lists suit sparse graphs and neighbour-driven traversal. State whether self-loops, duplicates and weights are supported rather than assuming every representation means the same graph model.

Traversal costs

DFS or BFS using lists is O(V + E). With a matrix, scanning V possible neighbours for every visited vertex gives O(V²) in a full traversal. Quoting O(V + E) without identifying representation can therefore misdescribe a matrix implementation.

Diagram or flowchart

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q1(h) · 3 marks

  Give an example of an adjacency list of a graph.

  Paper DS01 · page 1

View all matching source questions →

Recursive algorithm

1. Mark the starting vertex visited and process it.
2. Enumerate its neighbours in a stated order.
3. For each unvisited neighbour, recursively run DFS.
4. For a whole disconnected graph, start again at each still-unvisited vertex.

Worked example

For undirected edges 0–1, 0–2, 1–3 and 2–4, start at 0 and examine neighbour indices in ascending order. The DFS order is 0, 1, 3, 2, 4. From 1 it explores 3 before returning to 0 and considering 2.

Visited handling

Mark a vertex before exploring its outgoing neighbours. This prevents cycles from repeatedly recursing into an already discovered vertex. The same graph can have different valid DFS orders when start or neighbour order changes.

Applications

DFS supports reachability, component exploration and more specialised graph analyses. Detecting cycles or computing a topological order requires additional logic; a simple visited-only traversal should not be claimed to perform those tasks automatically.

Complexity

With adjacency lists, a full traversal processes V vertices and their stored edges, giving O(V + E) time. The supplied program uses a matrix and scans a whole row per visited vertex, giving O(V²). Visited storage and worst-case recursion depth are O(V). The fixed example graph is connected, so one starting call reaches every vertex.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define V 5
static const int graph[V][V] = {
    {0,1,1,0,0}, {1,0,0,1,0}, {1,0,0,0,1}, {0,1,0,0,0}, {0,0,1,0,0}
};
void dfs(int vertex, int visited[V])
{
    visited[vertex] = 1; printf("%d ", vertex);
    for (int next = 0; next < V; ++next) {
        if (graph[vertex][next] && !visited[next]) { dfs(next, visited); }
    }
}
void bfs(int start)
{
    int visited[V] = {0}, queue[V], front = 0, rear = 0;
    visited[start] = 1; queue[rear++] = start;
    while (front < rear) {
        int vertex = queue[front++]; printf("%d ", vertex);
        for (int next = 0; next < V; ++next) {
            if (graph[vertex][next] && !visited[next]) { visited[next] = 1; queue[rear++] = next; }
        }
    }
}

int main(void)
{
    int visited[V] = {0};
    printf("DFS: "); dfs(0, visited); putchar('\n');
    printf("BFS: "); bfs(0); putchar('\n');
    return 0;
}

DFS: 0 1 3 2 4 
BFS: 0 1 2 3 4

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q8(b) · 5 marks

  Explain DFS with an example.

  Paper DS03 · page 2
• March 2021 · Q4 · 15 marks

  Explain depth-first graph traversal with an example.

  Paper DS04 · page 1
• March 2022 · Q7(a) · 12 marks

  Give DFS algorithm with an example.

  Paper DS05 · page 1

View all matching source questions →

Algorithm

1. Mark the start and enqueue it.
2. While the queue is non-empty, dequeue a vertex and process it.
3. Enumerate its neighbours. Mark and enqueue each unvisited neighbour.
4. For a complete disconnected traversal, repeat from other unvisited starts.

Worked example

For edges 0–1, 0–2, 1–3 and 2–4, begin at 0. Enqueue 1 and 2 after processing 0. Process 1 and discover 3, then process 2 and discover 4. With ascending neighbour order, the output is 0, 1, 2, 3, 4.

Why FIFO matters

The queue processes all earlier discovered vertices before later ones. Consequently all distance-one vertices are handled before distance-two vertices. A stack would instead promote a latest-discovered branch and give DFS-like behaviour.

Shortest paths

BFS can record a predecessor and distance at discovery to obtain shortest paths measured in number of edges in an unweighted graph. This is not a universal least-cost algorithm for arbitrary weighted graphs. The demonstration prints traversal order only and does not claim to return a full path.

Complexity

Adjacency-list BFS is O(V + E). The supplied matrix demonstration is O(V²) because each processed vertex scans V possible neighbours. Its queue and visited array need O(V) space. Marking at enqueue ensures each vertex enters the queue at most once per traversal.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define V 5
static const int graph[V][V] = {
    {0,1,1,0,0}, {1,0,0,1,0}, {1,0,0,0,1}, {0,1,0,0,0}, {0,0,1,0,0}
};
void dfs(int vertex, int visited[V])
{
    visited[vertex] = 1; printf("%d ", vertex);
    for (int next = 0; next < V; ++next) {
        if (graph[vertex][next] && !visited[next]) { dfs(next, visited); }
    }
}
void bfs(int start)
{
    int visited[V] = {0}, queue[V], front = 0, rear = 0;
    visited[start] = 1; queue[rear++] = start;
    while (front < rear) {
        int vertex = queue[front++]; printf("%d ", vertex);
        for (int next = 0; next < V; ++next) {
            if (graph[vertex][next] && !visited[next]) { visited[next] = 1; queue[rear++] = next; }
        }
    }
}

int main(void)
{
    int visited[V] = {0};
    printf("DFS: "); dfs(0, visited); putchar('\n');
    printf("BFS: "); bfs(0); putchar('\n');
    return 0;
}

DFS: 0 1 3 2 4 
BFS: 0 1 2 3 4

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q9(b) · 5 marks

  Explain BFS with an example.

  Paper DS03 · page 2

View all matching source questions →

Shared requirements

Both need a graph representation, a starting rule and visited tracking. Both must restart at unvisited vertices if the task requires every component. State neighbour order when giving one exact printed sequence.

DFS

It follows a branch before backtracking. On the common five-vertex example with ascending neighbours, it gives 0, 1, 3, 2, 4. An explicit stack or recursion keeps unfinished work. The maximum active depth can reach V.

BFS

It explores level by level using a queue. The same example gives 0, 1, 2, 3, 4. Mark on enqueue to avoid duplicate pending entries. It naturally supports unweighted edge-distance calculations when distances are recorded.

Complexity

Both have O(V + E) time with standard adjacency lists and O(V²) with a matrix full traversal. Both can need O(V) auxiliary storage, although their practical pending-work patterns differ. The choice does not automatically reduce the representation’s own storage.

Choosing

Use BFS for level-order reachability or shortest numbers of unweighted edges. DFS is useful for deep exploration and as a base for analyses that require entering and finishing vertices. Neither basic traversal performs all possible graph applications without additional state or rules.

Reference table

Diagram or flowchart

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q8 · 10 marks

  Compare BFS and DFS for a graph.

  Paper DS01 · page 2
• August/September 2022 · Q7(b) · 7 marks

  Compare BFS and DFS with examples.

  Paper DS02 · page 1
• October 2020 · Q4(a) · 7 marks

  Differentiate BFS and DFS.

  Paper DS06 · page 1

View all matching source questions →

Contract

State whether vertices have fixed indices or external labels, whether edges are directed, and whether weights or duplicate edges are allowed. Define error results for invalid vertices and how a missing edge is represented.

Implementation choices

A fixed matrix provides direct adjacency tests and simple bounds checks for a small graph. Adjacency lists store only present edges and suit sparse neighbour traversal. Removing a vertex requires updating incident edges and any index mapping; it is not just deleting one display label.

Applications

1. Transport networks model connections and routes.
2. Social networks model relations between accounts or people.
3. Task-dependency graphs describe prerequisite relationships.
4. Communication graphs model devices and links.
5. Web link graphs model directed connections between pages.

Model carefully

An edge should represent a well-defined relation. Friendship may be undirected while following an account may be directed. Travel distance and fare are different weights. A DFS or BFS traversal answers reachability questions, but a particular application may require additional algorithmic steps.

Complexity

The ADT alone does not promise every operation is constant time. In a matrix, a valid edge lookup is O(1); a whole neighbour row scan is O(V). Lists have degree-based scans and O(V + E) storage. Separate the logical contract from the chosen performance characteristics.

Edges from the source table

2→3, 3→2, 5→3, 3→4, 2→5, 5→2, 5→1, 1→4, 5→4 and 4→5. Flight numbers distinguish the source rows; the unweighted graph records the stated endpoint relationships.

Adjacency lists

1. 1: [4]
2. 2: [3, 5]
3. 3: [2, 4]
4. 4: [5]
5. 5: [1, 2, 3, 4]

Matrix interpretation

Use rows as origins and columns as destinations in city-index order 1 through 5. A 1 records an outgoing connection; zero means that directed edge was not supplied. The table below is intentionally not made symmetric unless reverse flights actually appear.

Checks

There are ten 1 entries, matching the ten distinct supplied directed edges. Row 5 has four outgoing flights. Column 5 has incoming edges from cities 2 and 4. No self-flight is present, so the diagonal entries are zero.

Representation cost

A matrix stores 25 entries for these five cities. The adjacency lists store five vertex headers plus ten outgoing neighbour entries. General matrix space is O(V²); list space is O(V + E). No distance or fare is provided, so adding weights would invent information not present in the paper.

Reference table

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q8(a) · 5 marks

  Represent the supplied five-city flight network as a directed graph, adjacency matrix and adjacency list.

  Paper DS03 · page 2

View all matching source questions →