Graphs, Trees and Binary Search Trees

Graphs

Definition

A graph is a non-linear data structure consisting of nodes (vertices) connected by edges.

Key Point

Graph Types:
• Undirected: Edges have no direction (bidirectional)
• Directed: Edges have direction (one-way)
• Weighted: Edges have associated values/costs
• Unweighted: All edges equal
• Cyclic: Contains at least one cycle
• Acyclic: No cycles

Storing a Graph

A graph is stored in one of two ways. The examples below both store an undirected graph with six nodes and the edges A-B, A-C, B-D, B-E, C-F and E-F.

Definition

An adjacency matrix is a 2D array with a row and a column for every node. A 1 (or the weight of the edge) shows that two nodes are joined and a 0 shows that they are not.

An adjacency list stores, for each node, a list of the nodes it is joined to.

Example

Adjacency matrix:

Node	A	B	C	D	E	F
A	0	1	1	0	0	0
B	1	0	0	1	1	0
C	1	0	0	0	0	1
D	0	1	0	0	0	0
E	0	1	0	0	0	1
F	0	0	1	0	1	0

Adjacency list:

Node	Joined to
A	B, C
B	A, D, E
C	A, F
D	B
E	B, F
F	C, E

Key Point

Adjacency matrix
• Quick to check whether two nodes are joined: look up one cell
• Adding or removing an edge means changing a cell to 1 or 0
• Wastes memory when the graph has few edges, because every pair of nodes has a cell

Adjacency list
• Only stores the edges that exist, so it uses less memory when there are few edges
• Adding or removing an edge means adding or removing an item in a list
• Slower to check whether two nodes are joined, because a list has to be searched

In a directed graph the row is the node the edge leaves and the column is the node it arrives at, so the matrix is no longer symmetrical. In a weighted graph each 1 is replaced by the weight of the edge.

Trees

Definition

A tree is a hierarchical data structure with a root node and child nodes, forming a parent-child relationship. Trees are acyclic graphs.

Key Point

Tree Terminology:
• Root: The topmost node (no parent)
• Leaf: Node with no children
• Parent/Child: Directly connected nodes
• Siblings: Nodes with same parent
• Depth: Distance from root to node
• Height: Maximum depth of any leaf
• Subtree: Any node plus all its descendants

Binary Trees

Definition

A binary tree is a tree where each node has at most two children (left and right).

Binary Search Trees (BST)

Definition

A binary search tree is a binary tree where for every node:
• Left subtree contains only values less than the node
• Right subtree contains only values greater than the node

Worked Example

Worked Example: BST Operations

pseudocode

// BST Insert
procedure insert(node, value):
    if node == null then
        return new Node(value)
    end if
    
    if value < node.data then
        node.left = insert(node.left, value)
    else if value > node.data then
        node.right = insert(node.right, value)
    end if
    
    return node
end procedure

// BST Search
function search(node, target):
    if node == null then
        return false
    end if
    
    if target == node.data then
        return true
    else if target < node.data then
        return search(node.left, target)
    else
        return search(node.right, target)
    end if
end function

BST Search Complexity: O(log n) average, O(n) worst (unbalanced)

Storing a Binary Search Tree in an Array

A binary search tree can be held in an array in which each row stores a node: a left pointer, the data and a right pointer. A pointer is the index of the row that holds the child node, and a null pointer (often written -1) shows that there is no child on that side.

Worked Example

Worked Example: A Tree as an Array

The values 50, 30, 70, 20 and 40 are added in that order. 50 is the root.

Index	Left pointer	Data	Right pointer
0	1	50	2
1	3	30	4
2	null	70	null
3	null	20	null
4	null	40	null

Adding 60:
• Store 60 in the next free row, index 5, with both of its pointers null
• Start at the root: 60 is greater than 50, so follow the right pointer to index 2
• 60 is less than 70 and the left pointer of 70 is null, so set that left pointer to 5

Removing a Node from a Binary Search Tree

What has to change depends on how many children the node has. The tree must still be in order afterwards.

Key Point

Node being removed	What to do	Example in the tree above
A leaf (no children)	Set the pointer in its parent to null	Remove 20: the left pointer of 30 becomes null
One child	Change the pointer in its parent so that it points to the child instead	Once 60 has been added, remove 70: the right pointer of 50 changes to point to 60
Two children	Replace its data with the smallest value in its right subtree, then remove that node	Remove 30: it is replaced by 40, and the old 40 leaf is removed

Tree Traversals

Worked Example

Tree Traversal Methods:

pseudocode

// In-order (Left, Root, Right) - gives sorted order for BST
procedure inOrder(node):
    if node != null then
        inOrder(node.left)
        print(node.data)
        inOrder(node.right)
    end if
end procedure

// Pre-order (Root, Left, Right)
procedure preOrder(node):
    if node != null then
        print(node.data)
        preOrder(node.left)
        preOrder(node.right)
    end if
end procedure

// Post-order (Left, Right, Root)
procedure postOrder(node):
    if node != null then
        postOrder(node.left)
        postOrder(node.right)
        print(node.data)
    end if
end procedure

Depth-First and Breadth-First Traversal

Graphs and trees are both traversed in one of two ways. A graph can contain cycles, so a list of visited nodes is kept to make sure that no node is visited twice.

Definition

A depth-first traversal follows one path as far as it can go, then backtracks to the most recent node that still has an unvisited neighbour. It uses a stack to remember the nodes to return to.

A breadth-first traversal visits all the neighbours of the start node, then all of their neighbours, working outwards one level at a time. It uses a queue to hold the nodes waiting to be visited.

Worked Example

Worked Example: Traversing the Graph from Node A

This uses the six-node graph stored earlier, taking neighbours in alphabetical order.

Traversal	Structure used	Order visited
Breadth-first	Queue	A, B, C, D, E, F
Depth-first	Stack	A, B, D, E, F, C

Breadth-first:
• Visit A and add its neighbours B and C to the queue
• Take B from the front of the queue, visit it and add D and E to the back
• Take C, visit it and add F
• Take D, then E, then F. None of them has a neighbour that is not already visited or queued

Depth-first:
• Visit A, then its first unvisited neighbour B, then B's first unvisited neighbour D
• D is a dead end, so backtrack to B and visit E
• From E visit F, and from F visit C
• Every node has been visited, so the traversal ends

Key Point

On a tree:
• Breadth-first visits the root, then each level in turn from left to right. For the tree with root 50 above: 50, 30, 70, 20, 40
• Depth-first in OCR questions means post-order: left subtree, right subtree, then the node, so the root is visited last. For the same tree: 20, 40, 30, 70, 50

Exam Tip

When to use each structure:
• Array: Fixed size, frequent random access
• List: Variable size, frequent insertions at end
• Stack: Undo operations, expression evaluation, backtracking
• Queue: BFS, scheduling, buffering
• Linked List: Frequent insertions/deletions, unknown size
• Tree: Hierarchical data, searching (BST), sorting
• Graph: Networks, relationships, paths

	Left	Data	Right
0		Sligo
1		Dublin
2		Cork
3		Waterford
4		Galway
5		Limerick
6		Tralee
7		Dundalk

Graphs

Storing a Graph

Trees

Binary Trees

Binary Search Trees (BST)

Storing a Binary Search Tree in an Array

Removing a Node from a Binary Search Tree

Tree Traversals

Depth-First and Breadth-First Traversal

Exam questions on Graphs and Trees

Past paper questions