Trees and Graphs
Binary search trees with insert, search, delete and the three traversals; graphs held as matrices and lists; and breadth first against depth first search, each written and run on a small example you can follow by hand.
Binary trees and binary search trees
A tree is a data structure of nodes joined by edges, with one special node at the top, the root, and no loops. Each node can have child nodes below it. A node with no children is a leaf. Any node and everything below it is a subtree.
A binary tree allows each node at most two children, a left and a right. A binary search tree (BST) adds a rule that makes searching fast:
For every node, everything in its left subtree is smaller and everything in its right subtree is larger.
Searching follows the rule. At each node, compare: if the target is smaller go left, if larger go right, and stop when you find it or run out of tree. Each step discards a whole subtree, which is why a balanced tree of a million nodes needs only about twenty comparisons.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def contains(node, value):
while node is not None:
if value == node.value:
return True
if value < node.value:
node = node.left
else:
node = node.right
return False
root = None
for value in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, value)
print(contains(root, 35), contains(root, 65)) # True FalseThree ways to visit every node
A traversal visits every node exactly once. The three depth first orders differ only in when the node itself is visited, relative to its two subtrees.
| Traversal | Order | For the tree above | Use |
|---|---|---|---|
| Pre-order | root, left, right | 50 30 20 40 35 70 60 80 | Copying a tree |
| In-order | left, root, right | 20 30 35 40 50 60 70 80 | Reading a BST in sorted order |
| Post-order | left, right, root | 20 35 40 30 60 80 70 50 | Deleting a tree, and postfix expressions |
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def pre_order(node):
if node is None:
return []
return [node.value] + pre_order(node.left) + pre_order(node.right)
def in_order(node):
if node is None:
return []
return in_order(node.left) + [node.value] + in_order(node.right)
def post_order(node):
if node is None:
return []
return post_order(node.left) + post_order(node.right) + [node.value]
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
root = None
for value in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, value)
print(pre_order(root))
print(in_order(root))
print(post_order(root))
print("height", height(root))The in-order result is sorted, which is the whole point of the structure: inserting into a BST and reading it in order sorts the data.
Deleting a node
There are three cases, and the third is the one that needs thought.
| The node has | Do |
|---|---|
| No children | Remove it |
| One child | Replace it with that child |
| Two children | Replace its value with its in-order successor, the smallest value in its right subtree, and delete that node instead |
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def in_order(node):
if node is None:
return []
return in_order(node.left) + [node.value] + in_order(node.right)
def delete(node, value):
if node is None:
return None
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = node.right
while successor.left is not None:
successor = successor.left
node.value = successor.value
node.right = delete(node.right, successor.value)
return node
root = None
for value in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, value)
root = delete(root, 20) # a leaf
root = delete(root, 40) # a node with one child, 35
root = delete(root, 50) # the root, which has two children
print(in_order(root), root.value)Deleting the root, 50, leaves a gap that is filled by 60: the smallest value in the right subtree, and the only value that keeps everything on its left smaller and everything on its right larger.
The tree must stay balanced
A search is fast only if the tree is balanced, with its two sides about the same height. Add already sorted data and every value is larger than the last, so every node goes to the right and the tree becomes a linked list with a search time proportional to the number of nodes.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
sorted_order = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
balanced_order = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
for name, order in [("sorted", sorted_order), ("balanced", balanced_order)]:
root = None
for value in order:
root = insert(root, value)
print(name, "order gives a tree of height", height(root))The same fifteen values, two different heights. Real systems use self balancing trees that rearrange themselves as they grow, so the worst case never happens.
An expression tree
A tree can hold an arithmetic expression, with operators in the inner nodes and numbers in the leaves. Evaluating it is recursion, and a post-order traversal gives Reverse Polish notation.
tree = ("*", ("+", 3, 4), 2)
def evaluate(node):
if isinstance(node, tuple):
operator, left, right = node
a = evaluate(left)
b = evaluate(right)
if operator == "+":
return a + b
if operator == "-":
return a - b
if operator == "*":
return a * b
return a / b
return node
def postfix(node):
if isinstance(node, tuple):
operator, left, right = node
return postfix(left) + " " + postfix(right) + " " + operator
return str(node)
print(evaluate(tree), postfix(tree))Graphs
A graph is a set of vertices (nodes) joined by edges (arcs). Where a tree must have a root and no loops, a graph can connect anything to anything. A tree is simply a connected graph with no cycles.
| Term | Meaning |
|---|---|
| Directed | Edges have a direction, like one way streets or "follows" |
| Undirected | Edges go both ways, like friendships |
| Weighted | Each edge has a value, such as a distance or a cost |
| Path | A sequence of edges from one vertex to another |
| Cycle | A path that returns to where it started |
| Connected | There is a path between every pair of vertices |
| Degree | The number of edges meeting a vertex |
Graphs model anything that is a set of things with relationships between them: roads and junctions, network cables and routers, people and friendships, web pages and links, tasks and the order they depend on.
Storing a graph
The graph used through the rest of this topic has six vertices and seven edges:
A --- B
| |
C --- D --- F
| |
E ----------+An adjacency matrix is a table with a row and a column for every vertex. A 1 in row X, column Y means there is an edge between them.
An adjacency list stores, for every vertex, only the vertices it is joined to.
vertices = ["A", "B", "C", "D", "E", "F"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"),
("C", "E"), ("D", "F"), ("E", "F")]
matrix = [[0] * 6 for _ in range(6)]
adjacency = {v: [] for v in vertices}
for a, b in edges:
matrix[vertices.index(a)][vertices.index(b)] = 1
matrix[vertices.index(b)][vertices.index(a)] = 1
adjacency[a].append(b)
adjacency[b].append(a)
print(" ", " ".join(vertices))
for v, row in zip(vertices, matrix):
print(v, "", " ".join(str(x) for x in row))
print(adjacency)
print({v: len(adjacency[v]) for v in vertices}) # the degree of each vertexAn undirected graph's matrix is symmetric: the table is the same flipped over its diagonal. The degree of a vertex is the sum of its row.
| Adjacency matrix | Adjacency list | |
|---|---|---|
| Memory | One cell for every pair of vertices: V times V | One entry per edge: V plus E |
| Is there an edge between X and Y? | Immediate | Search X's list |
| List all the neighbours of X | Scan a whole row | Read X's list |
| Best for | Dense graphs, with many edges | Sparse graphs, with few |
A road network of a million junctions, where each junction meets about four roads, would need a matrix of a million million cells and a list of about four million entries. Almost every real graph is sparse.
Breadth first and depth first traversal
Visiting every vertex of a graph needs a rule for what to visit next, and one more thing a tree does not need: a record of the vertices already visited, because a graph can loop back and a traversal that forgets would go round forever.
Step 1 of 6 Visit 1: breadth first goes to A, taken from the front of the queue. Depth first goes to A, following one path as deep as it can.
Depth first: go as deep as you can
Follow one path until it runs out, then back up to the last place with an unexplored branch. A stack does the backing up, and recursion is a stack in disguise.
adjacency = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
"D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"]}
def depth_first(graph, vertex, visited=None):
if visited is None:
visited = []
visited.append(vertex)
for neighbour in graph[vertex]:
if neighbour not in visited:
depth_first(graph, neighbour, visited)
return visited
def depth_first_stack(graph, start):
visited = []
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.append(vertex)
for neighbour in reversed(graph[vertex]):
stack.append(neighbour)
return visited
print(depth_first(adjacency, "A"))
print(depth_first_stack(adjacency, "A"))Breadth first: all the neighbours first
Visit the start, then everything one step away, then everything two steps away. Each ring is finished before the next begins. A queue keeps the order.
from collections import deque
adjacency = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
"D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"]}
def breadth_first(graph, start):
visited = [start]
queue = deque([start])
while queue:
vertex = queue.popleft()
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
return visited
print(breadth_first(adjacency, "A"))Shortest path in an unweighted graph
Because breadth first search finishes every vertex one step away before any that is two steps away, the first time it reaches a vertex is by a shortest route (fewest edges). Remembering where each vertex was reached from lets you read the path back.
from collections import deque
adjacency = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
"D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"]}
def shortest_path(graph, start, goal):
came_from = {start: None}
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex == goal:
break
for neighbour in graph[vertex]:
if neighbour not in came_from:
came_from[neighbour] = vertex
queue.append(neighbour)
if goal not in came_from:
return None
path = []
while goal is not None:
path.append(goal)
goal = came_from[goal]
return path[::-1]
print(shortest_path(adjacency, "A", "F"))Choosing between them
| Depth first | Breadth first | |
|---|---|---|
| Keeps its place with | A stack, or recursion | A queue |
| Explores | One branch to its end, then backs up | All vertices one step away, then two |
| Finds the shortest path (fewest edges) | No | Yes |
| Memory | Proportional to the longest path | Proportional to the widest level |
| Typical use | Does a path exist, finding cycles, solving mazes, ordering tasks | Fewest hops, social network distance, web crawling |
State the data structure, then write the order the vertices are visited and, at each step, the contents of the stack or queue. If two neighbours are possible, take them in the order the question gives, usually alphabetical. A change of that order changes the answer.
- Breadth first: visit everything one step away, then everything two steps away, and so on. It uses a queue.
- Depth first: follow one branch as far as it goes, then back up and try the next. It uses a stack, or recursion.
Key terms you must be able to define
- Tree
- A connected data structure of nodes and edges with a single root and no cycles.
- Binary search tree
- A binary tree in which every node's left subtree holds smaller values and its right subtree holds larger values.
- Root
- The node at the top of a tree, which has no parent.
- Leaf
- A node of a tree that has no children.
- Traversal
- Visiting every node of a data structure exactly once in a defined order.
- In-order traversal
- Visiting the left subtree, then the node, then the right subtree. For a binary search tree this gives sorted order.
- Graph
- A set of vertices joined by edges, which may be directed or undirected, weighted or unweighted.
- Adjacency matrix
- A table with a row and column for each vertex, with 1, or the weight, where there is an edge.
- Adjacency list
- A record, for each vertex, of the vertices it is joined to.
- Breadth first search
- A traversal that visits all vertices one step from the start, then two steps away, using a queue.
- Depth first search
- A traversal that follows one path as far as possible before backing up, using a stack or recursion.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
Trees and graphs are always examined as a trace, a drawing and a comparison, so practise all three by hand.
- Apply the BST rule at every node as you insert: smaller left, larger right
- Write each traversal as its rule first, and then the order of nodes, for the same tree
- Say that in-order traversal of a binary search tree returns the values in sorted order
- Justify matrix against list with the graph's density: dense graphs suit a matrix, sparse ones a list
- Name the data structure behind each traversal, and why, when asked to trace breadth first or depth first
Mistakes that cost marks here
- Putting a smaller value on the right of its parent when drawing a binary search tree.
- Mixing up pre-order, in-order and post-order, which differ only in where the root goes.
- Forgetting to record visited vertices, so the traversal of a graph with a cycle never ends.
- Saying depth first search finds the shortest path.
- Choosing an adjacency matrix for a large sparse graph, where it wastes most of its memory.
Every file system you have used is a tree: one root, with folders inside folders. The web is a graph, because pages link to each other in loops. Google's first ranking idea, PageRank, was a calculation over that graph of links.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LIn-order: 10, 25, 30, 40, 50, 60, 70
- LThe in-order traversal is in ascending order
- LPost-order: 10, 30, 25, 50, 70, 60, 40
- LIn post-order each node is visited after both of its subtrees, so the root 40 is last
The tree has 40 as the root, 25 and 60 as its children, 10 and 30 under 25, and 50 and 70 under 60. An in-order traversal visits the left subtree, the node, then the right subtree, which gives 10, 25, 30, 40, 50, 60, 70, the values in ascending order. A post-order traversal visits the left subtree, the right subtree and then the node, which gives 10, 30, 25, 50, 70, 60, 40, with the root last.
- LDefines a function with the node as a parameter
- LBase case: an empty tree has 0 nodes
- LRecursive case: counts the left subtree and the right subtree
- LAdds 1 for the current node and returns the total
class Node:
def __init__(self, left=None, right=None):
self.left = left
self.right = right
def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
tree = Node(Node(Node(), None), Node())
print(count_nodes(tree), count_nodes(None))The base case is an empty tree, which has no nodes. Otherwise the answer is one for this node plus the number of nodes in each subtree. The calls shown print 4 and 0.
- LA matrix needs 1 000 times 1 000, which is 1 000 000, cells
- LMost of the cells would be 0, so the matrix wastes memory for a sparse graph
- LAn adjacency list needs entries only for the edges and so uses far less memory
- LA matrix tells you whether two vertices are joined immediately, whereas a list must be searched
An adjacency matrix would need a cell for every pair of vertices, 1 000 times 1 000, which is 1 000 000 cells, and with only 2 000 edges almost all of them would be 0. This graph is sparse, so the matrix wastes a lot of memory. An adjacency list stores only the edges, about 4 000 entries as each edge appears for two vertices, so it uses far less memory. The one advantage of the matrix is that it tells you if two vertices are joined immediately, whereas with the list the neighbours of one vertex must be searched. For this graph the list is the better choice.
| Vertex | Neighbours |
|---|---|
| A | B, C |
| B | A, D |
| C | A, D, E |
| D | B, C, F |
| E | C, F |
| F | D, E |
- LBreadth first: A, B, C, D, E, F
- LThe breadth first traversal uses a queue
- LDepth first: A, B, D, C, E, F
- LThe depth first traversal uses a stack or recursion, going as deep as possible before backing up
A breadth first traversal visits A, then the neighbours of A, B and C, then the unvisited neighbours of B and C, which are D and E, and finally F, so the order is A, B, C, D, E, F. It uses a queue. A depth first traversal goes from A to B, then from B to D, from D to C, from C to E and from E to F, so the order is A, B, D, C, E, F. It uses a stack, or recursion, and goes as deep as it can before backing up.
- LEach new value is larger than the one before, so it is always added to the right
- LThe tree becomes a long chain, like a linked list
- LA search may then have to visit every node, so it takes time proportional to the number of nodes instead of the logarithm
- LIt can be avoided by keeping the tree balanced, such as using a self balancing tree, or by inserting values in a random or median first order
If the values arrive in order, each new value is larger than all those already in the tree, so it is always added on the right and the tree becomes a long chain, no better than a linked list. A search may then need to visit every node, so the time is proportional to the number of nodes rather than to the logarithm of the number of nodes. The problem can be avoided by keeping the tree balanced, for example by using a self balancing tree that rearranges itself as values are added, or by inserting the values in a random order or middle value first.