Trees and Graphs

1 A binary search tree is built by adding the values 40, 25, 60, 10, 30, 50, 70 in that order to an empty tree. State the order in which the values are visited by an in-order traversal, and by a post-order traversal. 4

One mark for each of the following, to a maximum of 4.

• In-order: 10, 25, 30, 40, 50, 60, 70
• The in-order traversal is in ascending order
• Post-order: 10, 30, 25, 50, 70, 60, 40
• In post-order each node is visited after both of its subtrees, so the root 40 is last

Model answer. 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.

2 Write a recursive Python function called count_nodes that takes the root of a binary tree and returns the number of nodes in it. An empty tree is represented by None, and each node has the attributes left and right. 4

One mark for each of the following, to a maximum of 4.

• Defines a function with the node as a parameter
• Base case: an empty tree has 0 nodes
• Recursive case: counts the left subtree and the right subtree
• Adds 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))

3 A graph has 1 000 vertices and 2 000 edges. Compare using an adjacency matrix and an adjacency list to store it. 4

One mark for each of the following, to a maximum of 4.

• A matrix needs 1 000 times 1 000, which is 1 000 000, cells
• Most of the cells would be 0, so the matrix wastes memory for a sparse graph
• An adjacency list needs entries only for the edges and so uses far less memory
• A matrix tells you whether two vertices are joined immediately, whereas a list must be searched

Model answer. 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.

4 The graph shown is stored as an adjacency list. Neighbours are always taken in alphabetical order. State the order in which the vertices are visited by a breadth first traversal starting at A, and by a depth first traversal starting at A. 4

One mark for each of the following, to a maximum of 4.

• Breadth first: A, B, C, D, E, F
• The breadth first traversal uses a queue
• Depth first: A, B, D, C, E, F
• The depth first traversal uses a stack or recursion, going as deep as possible before backing up

Model answer. 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.

5 Explain why a binary search tree that is built from a list of values that was already in order is not efficient to search, and describe how this problem can be avoided. 4

One mark for each of the following, to a maximum of 4.

• Each new value is larger than the one before, so it is always added to the right
• The tree becomes a long chain, like a linked list
• A search may then have to visit every node, so it takes time proportional to the number of nodes instead of the logarithm
• It 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

Model answer. 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.