CS43 : How many gardeners do you know?


In this section we will consider two very important data structures - graphs and trees.

We are learning ...
  • About graphs
  • About trees
  • About traversal algorithms
So that we can ...
  • Represent graphs as data structures
    - representing complex relationships
    - typical uses
    - terms
  • Represent graphs
    - Adjacency matrix and adjacency list
    - Advantages and disadvantages of both
  • Apply breadth first and depth first graph traversal algorithms and describe typical applications of both
    - depth first : navigating a maze
    - breadth first : shortest path for unweighted graph
  • Describe and represent trees
    - Connected, undirected graph with no cycles
    - Rooted tree where every vertex is directed away from the root
  • Describe binary trees
    - Binary tree (rooted tree with <= 2 children per node)
    - Representing binary trees using pointers
    - Typical uses
  • Trace tree traversal algorithms and their applications
    - pre-order
    - in-order
    - post-order
  • Describe and implement route / pathfinding algorithms
    - Dijkstras shortest path algoritm
    - A* algorithm

Activity 1 A challenge? (45)

Way back in the AS part of the course, we met the 'Poor cartographer' - a problem in graph colouring. We actually used a game called Floodfill (which I'm not expecting you to play now, but you probably will!) A solution to this problem involves drawing graphs - connected diagrams which are used, in this case, to represent barred relationships between areas to be coloured. Using this data structure and a particular algorithm, we were able to deduce a solution (though not always optimal) to the problem.

http://csunplugged.org/graph-colouring/
The 'Poor Cartographer'

Task 1.1
 The Ichthyophile Problem

View the puzzle, The Ichthyophile Problem and see if you can remember the method we used to solve it ...

OUTCOME : No checkpoint, just a reminder of one application of graph theory.

Graphs are an abstraction which are used to represent real world problems in a way which makes them easy to solve either logically or mathematically. The first ever application of graph theory (and hence it's conception) occurred in the early 18th century and is attributed to the mathematician Leonhard Euler.


Task 1.2
 The Königsberg Bridge problem

The Königsberg Bridge problem is a recreational maths puzzle set in the old Prussian city of Königsberg (now Kaliningrad, Russia) developed by Leonhard Euler which led to the development of graph theory.

Created by Simon Kneebone, Australian illustrator

In the early 18th century, the citizens of Königsberg spent their days walking on the intricate arrangement of bridges across the waters of the Pregel (Pregolya) River, which surrounded two central landmasses connected by a bridge (1). Additionally, the first landmass (an island) was connected by two bridges (2 and 3) to the lower bank of the Pregel and also by two bridges (4 and 5) to the upper bank, while the other landmass was connected to the lower bank by one bridge (6) and to the upper bank by one bridge (7), for a total of seven bridges.

According to folklore, the question arose of whether a citizen could take a walk through the town, visiting all four landmasses in such a way that each bridge would be crossed exactly once.

Can you find a route? If not, can you explain why? You might want to research online to find the answer.

OUTCOME : Discussion only, no checkpoint.


Activity 2 About graphs (and trees) (60)

There is lots of terminology surrounding graphs in computer science. There is a document in the lesson resources called Graph and tree definitions. Download it and keep a copy stuck in your notebooks for reference. The list is not meant to be exhaustive (even though it's very long) as this discrete mathematics topic is a whole course in itself!

Graphs are normally drawn with sequenced circles (with or without labels) to represent the vertices and lines (with or without arrows, labels or weights) to represent the edges. The diagram shows a representation of some graph components.
https://drive.google.com/file/d/0B83yXMOilskaYkJYUDZGMVFVLTg/view?usp=drive_web
Click to engage

I think I've covered everything! If you are a further mathematician and you are raging, please let me know. I'm not going to ask you to do anything particular with these definitions now, but keep this list in mind when you are working throught the rest of the topic. Lol!

Task 2.1
 Learning yourself - the flipped classroom

Visit the MyMaths website and log in with your schools username and password (ask your teacher). Navigate to ...

> A Level
> Decision 1
> Graphs

... and work through as much of this section as you can in the time allocated, making notes and trying the exercises. It's true that a lot of this content is outside the A Level specification but it certainly won't do you any harm to learn it. Graph theory is a threshold concept in Computer Science which you will meet again and again.

OUTCOME : Notes on, and a deeper understanding of, Graphs


Activity 3 Representing complex relationships (40)

In Computer Science, graphs are an representation abstraction which allow us to model diverse complex relationships in a consistent way allowing us to apply similar algorithms to every situation in order to solve problems presented by them

Chain links and the Oracle of Bacon

In 1929, a Hungarian author called Frigyes Karinthy published a short story called 'Chains' where he introduced the concept of 'six degrees of separation'. Later on, film buffs all over the world invented the parlour game 'Six degrees of Kevin Bacon' where they challenged each other to connect any Hollywood actor to Kevin Bacon through the least number of films possible.

Task 3.1
 Six degrees

Two steps in this activity ...
  1. Download and read the short story Chain links by Frigyes Karinthy which is in the lesson resources. Think about the implications!

  2. Visit the Oracle of Bacon website and challenge yourself to connect your favourite Hollywood actor to Kevin Bacon in less than six steps. In fact, it turns out that 99.97% of all 2.2 million listed Hollywood actors have a 'Bacon number' of six or less. Amazing.

OUTCOME : Appreciation of Kevin Bacon. No checkpoint.

Diverse systems

It turns out that wherever there are relationships between 'things' a graph can be drawn which connects them. For instance ...

System Vertices Edges 
World Wide Web Web pages  Hyperlinks 
Computer networks  Switches, hubs, computers  Network cables 
Social networks  People and groups  Friendships / relationships 
Electrical circuits  Components  Wires 
Transport routes  Towns, villages, intersections  Roads, paths 
Air routes  Airports  Air routes 
Chemical compounds  Atoms  Chemical bonds 
Timetables Students / Courses  Enrollment 
Flowchart  Flowchart symbols   Arrows indicating program flow 
Conflict situations  Entities in the conflict  Barred relationships 
Factors  Numbers  'Is a factor of' 
Network latency Components  Connections weighted with latency value 

... and there are literally hundreds more. Can you think of any?

Integer factors

Task 3.2
 Graph representations

Use Google Images to find graph representations of at least three of the systems from the list above. Prefix your images search with 'graph representation' so you find the correct type of image. Choose the images carefully and try not to run searchs for the same image as other students in your group (if you can).

Print out your three graphs for your notebooks. Compare your results with those of another student - make sure you see the similarities rather than the differences.

OUTCOME : Three graph representations of complex systems.


Activity 4 Representing graphs (250)

All graphs can be represented as a collection of vertices and the connections which exist between them. The properties of the vertices and connections define both the type of graph and it's behaviour.

Vertex and Edge Sets

Consider the following six graphs labelled a) through f) which cover most of the major graph types. We will use these graphs a lot over the next few tasks so you might want to print out the diagram for your notebooks.

https://drive.google.com/file/d/0B83yXMOilskad3E2Y3Q2TU9TTFE/view?usp=drive_web
Diagram A
Click to engage

In general, all graph definitions contain a 'vertex set' made up of one or more vertex objects. In it's simplest form, this will be a list of unique vertex 'id' values but could be expanded as a list of tuples if more information about each vertex is required, such as labels for instance.

vertices = {id[,id]*}
vertices = {(id,value[,value]*)[,(id,value[,value]*)]*}

For instance, the graphs in Diagram A can be represented using one of two different vertex sets ...
  • Graphs a), b), c) and d) have the vertex set v = {1,2,3,4,5} 
  • Graphs e), f), g) and h) have the vertex set v = {(1,Y),(2,P),(3,G),(4,B),(5,G)} where the letters represent the colours of the vertices as their labels.
There are two widely accepted methods for representing the connections in a graph ...
  • Adjacency list
  • Adjacency matrix
Graph Implementations (7:14)


Task 4.1
Vertex and edge sets

The video shows how to represent a weighted, directed graph as an adjacency matrix and an unweighted, undirected graph as an adjacency list - i.e. it only shows a method for representing edges for graphs a) and d) from Diagram A in one of the two ways (but I'm not telling you which).

In your notebooks : Your mission, should you choose to accept it, is to draw both adjacency matrix and adjacency list representations for graphs a), b), c) and d) from Diagram A.

Hints!
  • The adjacency matrix for an unweighted graph only contains 0 and 1 to indicate the absence or presence of a connection between vertices. For a weighted graph, where the connection would be 1 it contains the weights and where the edge would have been 0 it either contains 0 (as in the video) although, you will often see the weight of an unconnected edge represented by (infinity) in textbooks. However, since there is no way of indicating infinity in Python (that I can find although you can test for it with math.isinf()), you can either use 0, a large number like 999 or even a letter.
  • The adjacency matrix for an undirected graph is symmetrical about the centre diagonal and vice versa.
  • An adjacency list for an undirected graph will always state both pairs for each connection, i.e A:B and B:A but if the graph is directed, at least one of these (across all vertices) will be missing.
  • An adjacency list for a weighed graph will have a set of tuples for each connection, e.g. A:(B,W) where W represents the weight on the connection.
In your notebooks : If you are still hungry, answer the following questions.
  1. What feature would the adjacency matrix have if the graph contained 'loops' (pseudograph)? Can you draw an example and give it's adjacency matrix to prove your point?
  2. What about an unweighted multigraph (multiple edges between the same vertices)?
  3. It is possible that a directed graph could have different weights on the forward and reverse connections between two vertices. For instance ...


    What would the adjacency matrix and adjacency list for this little graph look like?
OUTCOME : Matrix and list representation of the connections in Graph a), b), c) and d) plus hungry questions?


Adjacency list vs adjacency matrix

There are certain situations where an matrix is beneficial and certain where a list is best.

Task 4.2
 List vs Matrix?

Any graph representation / implementation must allow for the following operations ...
  • Querying the existence of a node / connection
  • Adding a node / connection
  • Removing a node / connection
  • Altering a node / connection
... and should minimise the quantity of storage space required to hold the graph.

Can you describe the pro's and con's of both these methods of representing a graph? You may wish to use the following website to help you.

OUTCOME : Description of the pro's and con's of adjacency lists and matrices.



This is the fun bit! All graph representation require that you store information about both the vertices and the edges which connect them. There are various ways of accomplishing this but by far the most flexible is through the use of a vertex class which is defined by it's ID and contains a dictionary of weighted 'connections' (general name for edges / arcs) and a graph class which is built from a dictionary of vertex objects identified by their vertex ID plus a Boolean attribute which classifies the graph as directed / undirected.

Task 4.3
 Vertex and graph class

  • Open up the Python programming environment, IDLE

  • Download and print yourself a copy of the Graph data structure infosheet which is available from the lesson resources. This explains how the vertex and graph class are constructed.

  • Download the graphClass(template).py file from the lesson resources and save it in your userspace. Open the file for editing by right clicking and choosing 'Edit with IDLE'.

  • Now try to complete the class methods for the vertex and graph classes! If you get stuck ask for help. Test your classes out by trying to create one of the graphs from Diagram A.

  • When you have finished (or had enough), ask your teacher for a copy of the completed graphClass.py file (not available from the lesson resources) and compare what you have done to what he / she has done.

    Print a copy for your notebooks and retain script for use later on.

  • I've also implemented the following extra method in the graph class to allow you to import a special graph notation dictionary to speed up your graph creation tasks!

    def importGraph(self,d):
        for key in d.keys():
            self.addVertex(key[0],key[1])
        for key,value in d.items():
            for connection in value:
                self.addConnection(key[0],connection[0],connection[1])

    The notation for d is {(v,value):[(x,w)*]*} where v is a vertex id, value is its value, x is the connected node and w is its weight. Make sure that the dictionary is structured correctly - there is no error checking in this routine so it will fail!

    At the prompt : Try this dictionary to start which represents graph a) in Diagram A.

    >>> ga = graph()
    >>> ga.importGraph({(1,0):[(2,1),(3,1),(4,1),(5,1)],
                        (2,0):[(4,1)],
                        (3,0):[(4,1)],
                        (4,0):[],
                        (5,0):[]})

    >>> print(ga)

    At the prompt : Notice that you don't have to specify each direction - because the graph is undirected, it automatically creates the reverse connections. Notice that the weight of each connection is 1. Now try this one which represents graph b) in Diagram A.

    >>> gb = graph(directed=True)
    >>> gb.importGraph({(1,0):[(2,1)],
                        (2,0):[],
                        (3,0):[(1,1)],
                        (4,0):[(1,1),(2,1),(3,1)],
                        (5,0):[(1,1)]})

    >>> print(gb)

    Since this graph is directed, it won't create the reverse connections because there aren't any. So there.

  • Create graphs c) through h) in the same way. Complete Graph Implementations worksheet whilst you are working which is available in the lesson resources.

    When you have finished, print your worksheet out for your notebooks

  • Now, investigate as many of the graph class methods as you can. Do not move on until you are satisfied that you understand how this class works. You do not need to document your work, but make sure you do it!

OUTCOME : Printed vertex and graph class implementations plus Graph Implementations worksheet.


Graph traversal / searching

Traversal of a graph involves visiting every node starting at some arbitrary node, called the root of the graph. Searching involves looking for a node starting at some particular node. Traversal / searching traditionally takes place in one of two different ways - so called breadth or depth first. Be careful - the terms 'traverse' and 'search' are often confused.

Graph Traversals (9:52)

Depth first traversal

Note to self : These scripts *seems* wrong - review and correct

DFT uses a stack data structure to keep track of discovered vertices. As we shouldn't really alter the graph to 'mark the vertex as visited', we also need a simple list to keep track of the vertices we have visited in the order we visited them. In the video, 'John' perform a recursive depth first traversal, using a stack. In practice, no explicit stack is needed as the recursion takes care of that bit. Depth first traversal is suited to recursion, because it's 'deep'.

def dftR(G,n,visited=[]):
    """ Recursive depth first traversal """
    visited.append(n)
    for v in G.connections(n):
        if v not in visited:
            dftR(G,v,visited)
    return visited

You can perform a depth first traversal iteratively (many programmers would prefer this to reduce the risk of recursion depth errors for large graphs, especially in Python), but it is a little more complicated and the vertices are visited in a different order that they are in the recursive routine (but still in depth first order).

def dft(G,n):
    """ Iterative depth first traversal """
    stack   = [n]
    visited = []
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for x in G.connections(v):
                stack.append(x)
    return visited

Breadth first traversal

Note to self : Probably need to check these as well

BFT is not naturally suited to recursion since it does not have the 'depth' element that most recursive functions need - you can implement it recursively but it's more a theoretical exercise than a practical implementation. So we'll implement this iteratively. BFT is closely related to the iterative DFT apart form the use of a queue instead of a stack and the order in which you mark the vertices as visited.

def bft(G,n):
    """ Iterative breadth first traversal """
    queue   = [n]
    visited = [n]
    while queue:
        v = queue.pop(0)
        for x in G.connections(v):
            if x not in visited:
                queue.append(x)
                visited.append(x)
    return visited


Task 4.4
 DFT / BFT


Grab a copy of the graph class script

You should already have a copy of graphClass.py from the previous task. Make sure this is in a suitable folder in your documents.

Grab a copy of the graph traversal script

Download a copy of graphTraverse.py from the lesson resources and save it in the same folder as the graphClass.py file - the graphTraverse.py script imports the graphClass.py file so it needs to be in the same folder.

Inspect (and document?) the script

The graphTraverse.py script contains the following functions ...

  dftR(G,n,visited=[])
  Recursive depth first traversal on graph G starting at vertex n.

  dftRS(G,n,visited=[],stack=[])
  Recursive depth first traversal on graph G starting at vertex n with contrived stack.

  dft(G,n)
  Iterative depth first traversal on graph G starting at vertex n.

  dftS(G,n)
  Incomplete iterative depth first traversal on graph G starting at vertex n with contrived stack.

  bft(G,n)
  Iterative breadth first traversal on graph G starting at vertex n.

  bftQ(G,n)
  Incomplete iterative breadth first traversal on graph G starting at vertex n with contrived queue.

Demonstrate your understanding

I have also created a graph object, g to represent this graph to help you to investigate the traversal functions.


EASY : Run the script and convince yourself that the visited order of the vertices conforms with the concept of depth first and breadth first traversal. Try changing the starting node, n in the function calls and make sure that you agree with the order of traversal. Print out some evidence for your notebooks.

MODERATE : I have also included a contrived example for the recursive depth first traversal which includes a tail recursive stack (not needed, but nice to see nontheless) so that it works in the same way as 'John's video. Can you complete the remaining two incomplete functions, dftS(G,n) and bftS(G,n) to print out the stack and queue structures respectively?

HARDER : One issue with these implementations is that the order in which a particular vertices' neighbours are visited is random (due mainly to the way that the dictionary structure works). Can you amend the functions so that each vertices neighbours are dealt with in order?

HARDEST : The concept of a search is different to a traversal. A traversal always visits every vertex in the graph whereas a search might not because the destination vertex may be visited before every other vertex is discovered. However, if a search does result in every node being visited, then it is a traversal, by definition, and not a search, which is confusing.

Download the graphSearch.py script from the lesson resources and save it in the same folder as the graphClass.py script. The graphSearch.py script contains three incomplete functions ...

  dfsR(G,n,d,visited=[])
  Recursive depth first search of graph G from vertex n to vertex d.

  dfs(G,n,d)
  Iterative depth first search of graph G from vertex n to vertex d.

  bfs(G,n,d)
  Boolean, iterative breadth first search of graph G from vertex n to vertex d.

Your challenge is to complete these functions. Use the functions in traverse.py to help you but make sure that once the destination vertex, d, is visited, you terminate the search and return the visited list. 

Print out the graphTraverse.py script for your notebooks
Print out the graphSearch.py script for your notebooks.

OUTCOME : Print out of graphTraverse.py script together with evidence of running the traversals and possible extensions including alterations to the script and the graphSearch.py script as well.


Depth first traversal / search can be used to ...
  • Produce the 'minimum spanning tree' of a graph
  • Detect cycles in a graph (with some modification)
  • Find a (often suboptimal) path through the graph
  • Solve puzzles with only one solution (perfect mazes / trees)
Breath first traversal / search can be used to ...
  • Produce the 'minimum spanning tree' of a graph
  • Find the shortest path through a network (weighted graph)
  • Finding all neighbour nodes in a peer to peer network
  • Search engine crawlers
  • Find degrees of separation between two vertices, say in a social network


Task 4.5
 Adjacency matrix

So, the graph representation we've used here is an adjacency list. Your big challenge is to implement the graph and all it's related behaviours as an adjacency matrix. You might want to start with this Stack Overflow post ...

OUTCOME : Adjacency matrix graph implementation in Python.


Activity 5 Trees (260)

In mathematics, a tree is a "connected, undirected graph which contains no cycles or loops". An arbitrary tree is represented in the same way as a graph where the number of edges is always the same as the number of nodes. A rooted tree is hierarchical (like a family tree) and will have a root node with all other nodes branching away from it.

There is plenty more terminology associated with trees (which isn't in a handout) ...

Root : The node in the tree with the highest hierarchy or an arbitrary node to begin traversal 
Child : A node connected directly to another node when moving away from the root
Parent : The converse of child
Siblings : Group of nodes with the same parent 
Leaf : A node with no children 
Branch : A connection between parent and child. An edge. 

Task 5.1
 A rooted tree to label

Sketch the diagram below in your notebooks and label it using the terminology given.


OUTCOME : Labelled diagram of a rooted tree


Binary search trees

A binary search tree is a rooted, ordered, directed tree which has no more than two children per parent node. A binary tree is 'proper' if each internal node (i.e. not leaf nodes) has exactly two children.

Binary trees are ...
  • Useful for storing data with an inherently hierarchical structure;
  • Dynamic - it is easy to add and delete nodes;
  • Easy to search and sort;
  • Deep (man).
Binary trees are constructed in a different way to arbitrary tree which is simply a graph with no cycle. You do not treat them like graphs even though they look similar.

Task 5.2
 Constructing a binary search tree

For this activity, create a blank word processed document with a suitable header and footer.

The University of San Francisco, Computer Science Department has a fantastic visualisation applet on it's website which allows you to create a binary search tree ...

https://www.cs.usfca.edu/~galles/visualization/BST.html

Use the applet to create binary search trees for the following unstructured data sets (you have to  Insert  each item individually). Watch carefully how it is created.
  • F, T, J, C, B, E, W, G, X, D
  • 5, 7, 3, 15, 9, 12, 8, 16
Take a screenshot of each tree and paste this onto your word processed document. Add the corresponding data set underneath and explain how it was generated. Try deleting one node at random from each tree. Can you figure out how this works? Don't worry if you can't at this stage. Click  Skip Back  if you want to undo your changes and carry on investigating.

Then click the  Print  button on the applet and watch what it does. Write about what you have discovered in your word processed document.

Print out two copies of your word processed document for your notes.
Stick one in now and save the other one for later because you'll need it!

OUTCOME : Two binary search trees plus explanations.


A practical binary search tree

Each vertex in the tree (including the root vertex) must have a 'payload' / value and has the potential to have a parent, zero children (i.e. it's a leaf), a left child (which is ordinally less than the vertex), a right child (which is ordinally greater than the vertex) or both. That child vertex could itself be the root node of a separate subtree.

It is (relatively) easy to construct a binary search tree from vertex objects with a unique id, a 'value', and three pointers, one to the parent, a left child and a right child. If no parent or child vertex exists, the pointer will have a null value.

Binary search tree vertex object

As you can imagine, there are plenty of different ways of implementing this in practice, but I've chosen one which works similarly to the linked list abstract data structure which we have met before.

Task 5.3
 Investigating a binary search tree

  • Download a copy of the Tree data stucture infosheet and print this out for your notebooks. It lists all the properties and methods of the tree vertex class and the bst (binary search tree) class.

  • Open up the Python programming environment, IDLE

  • Download a copy of the binarySearchTreeClass.py script, save it to a suitable place in your documents, right click on it and 'Edit in IDLE'. Inspect the script and rubber duck it with your coding partner.


  • Now let's create a tree. Look back at the work you did in Task 5.2 where you created a binary search tree using an applet on the USFCA website for the following unstructured data ...

    F, T, J, C, B, E, W, G, X, D

    At the prompt : Create the tree by issuing the following comments at the prompt, pressing the  ENTER  key after each one.

    >>> t = bst()
    >>> data = ['F','T','J','C','B','E','W','G','X','D']
    >>> for item in data:
            t.insert(item)

    >>> print(t)

    You should get a beautiful table showing the vertices and the pointers which show how each one is connected to all the others and an indication of the root node. Print a copy of this table out for your notebooks and stick it in under a suitable title.

  • On the second copy of the binary search tree you printed out in Task 5.2, label the tree with the vertex ids from this table and stick this in along it in your notebooks. Are you happy that both these represent the same tree?

  • I've heavily commented the script to explain how it works. Investigate the bst.insert(v), bst.search(v) and bst.delete(v) functions alongside performing the same operations on the USFCA applet. I have set the deletion mode at 'p' for predecessor so that the deletion method is the same as the one used on the USFCA website, which should help.

    When you are satisfied how they work, write out your own algorithm for the insert, search and (possibly) delete methods in your notebook. You can use structured English, pseudocode or even a flowchart if you like.

  • Print out a copy of the script using Notepad++ to format the code nicely. You will have to print it landscape mode or else the comments will wrap over the line. Stick the script into your notebooks.

  • IMPORTANT SECTION

    Before we move on, it may be worth thinking about why we would bother to structure data in a binary search tree like this. Consider searching the unstructured list [F, T, J, C, B, E, W, G, X, D] and the binary search tree for each item in turn. How many 'comparisons' would you need to perform in each case?

    Write down your ideas in your notebooks.

OUTCOME : Evidence of creating a binary search tree and algorithms for insert, search and (possibly) delete. A copy of the script. Explanation of the benefit of using a binary search tree to structure data in this way.

There are plenty of other ways of implementing a binary search tree, just like there are plenty of ways of implementing a graph which are more straightforward than this. I've tried to give you a 'low level' implementation which doesn't involve more complex concepts. Once you understand the basics, it's easy to simplify your implementation to suit. Take a look in the extension activities for more tutorials which give you different approaches.



Binary tree traversal / searching

Trees can be traversed in the same way as graphs (well, they are graphs, aren't they?) In fact, traversing a graph produces a tree (but not always a binary tree).  We've looked at breadth first and depth first traversals of graphs in a previous section - remember that binary trees are constructed differently than graphs therefore they have to be traversed in a different way.

In a depth first traversal of a binary tree, you 'travel' down each branch as far as you can go working from left subtree to right subtree, backtracking when you reach a leaf node.

Depth first binary tree traversal

If you think of a depth first traversal of a binary tree as a journey clockwise, around the walls of a rather strange city, where the vertices are towers with three doors, facing West, South and East, you might see that there are three ways of 'visiting' each vertex. If we walk around our city going into each tower through each door we find, this is called a Euler Tour Traversal. You can perform one yourself if you like using Minecraft Euler Tour.zip which is available from the lesson resources.


There are three special cases of a Euler tour traversal ...
  • Only entering through the west doors, a so called 'Preorder Traversal'
  • Only entering through the south doors, a so called 'Inorder Traversal'
  • Only entering through the east doors, a so called 'Postorder Traversal' 



Task 5.4
 Binary Tree Traversals

  • Visit the Binary Tree Visualiser website. Create a binary search tree from the following list of unstructured data by  Insert ing each value. You can't add them all at once I'm afraid :(

    50, 46, 35, 67, 79, 20, 38, 65, 78, 80, 41

    Copy or screenshot the tree into your notebooks.

  • Perform a  To Preorder Array  traversal, watch what happens and write the list of values in your notebooks.

  • Perform an  To Inorder Array  traversal, watch what happens and write the list of values in your notebooks.

  • Perform a  To Postorder Array  traversal, watch what happens and write the list of values in your notebooks.

  • The three traversal methods are very similar, and recursive. Here are the algorithms ...

    subroutine : preorder
        start at root vertex
            return the value of the current vertex
            if the vertex has a left child, preorder traverse the left subtree
            if the vertex has a right child, preorder traverse the right subtree

    subroutine : inorder
            if the vertex has a left child, inorder traverse the left subtree
            return the value of the current vertex
            if the vertex has a right child, inorder traverse the right subtree

    subroutine : postorder
            if the vertex has a left child, postorder traverse the left subtree
            if the vertex has a right child, postorder traverse the right subtree
            return the value of the current node

    Notice that it's only the position of the
     return which changes - before any subtree traversal for preorder, as soon as no left subtree is discovered for inorder and as soon as no left or right subtree is discovered for postorder.

    Try visually tracing through each algorithm with the tree in front of you - can you see how they work?

    In your notebooks
    : Now copy these algorithms into your notebooks.

  • Download a copy of the binarySearchTreeTraverse.py script from the lesson resources. Save it in a suitable place in your documents, right click on the file and choose 'Edit with idle'. Look carefully at the functions and see that they are the same (barring syntactical sugar) as the algorithms above. Run the script and compare the output to the lists you wrote down in the previous steps - they should be the same.

  • Print out the script using Notepad++ and stick this in your notebooks.

  • Download and print the worksheet Tree Traversals and complete this without using any websites or scripts to help you - work it out for yourself. If you want to check whether you are correct, by all means do so, but not until you have tried the tasks manually. Stick the worksheet in your notebooks.

OUTCOME : Evidence that you have performs the three binary tree traversal methods on the tree provided, the algorithms copied into your notebook, the script printed and stuck in and a completed copy of the worksheet.


Applications of tree traversals

Remember that you can have two basic types of tree - arbitrary trees which are simply graphs without cycles and a specific case called a binary tree which is a rooted, ordered, directed tree which has no more than two children per parent node. Pre and postorder traversals make sense for all trees whereas inorder traversals can only be achieved using binary trees.

Preorder traversals

A preorder traversal is equivalent to a standard graph depth first traversal where the vertex is 'visited' first before its children are visited and can be applied to any tree. A preorder tree traversal can be used for ...
  • Inspecting all vertices before their children
  • Making an exact copy of a tree
  • Converting a mathematical expression tree into a prefix expression
  • Reading a book from beginning to end ...

Inorder Traversals

You can only perform inorder traversals on a binary tree (see this link). The inorder tree traversal can be used for ...
  • Returning the underlying data set in order (we've seen this!)
  • Generate an infix expression from mathematical expression tree

Postorder traversals

A postorder tree traversal is equivalent to a standard graph depth first search where the node is only 'visited' after it's children have been explored and can be applied to any tree. The postoder tree traversal can be used for ...
  • Inspecting all leaves before their parents
  • Deleting a tree from the leaves up
  • Generate a postfix expression from a mathematical expression tree
  • Calculating disk storage from files through directories to disk ...

Task 5.5
 Uses of tree traversals

Make notes on the uses of tree traversals from the lists above. Sketch the diagrams into your notebooks as well to help to explain the uses. Try to come up with some of your own examples as well if you can.

OUTCOME : Notes on the uses of tree traversals


You'll notice that all three traversal methods can be used to generate arithmetic expressions from mathematical expression trees. Consider the following binary expression tree traversals ...
https://drive.google.com/file/d/0B83yXMOilskadjB1aDhDdF9nVXc/view?usp=drive_web
Generates the prefix expression ... * + 5 6 - 8 3

https://drive.google.com/file/d/0B83yXMOilskaZEpwUHNoQmp3TVU/view?usp=drive_web
Generates the infix expression ... ((5+6)*(8-3))
Output '(' before traversing a left subtree
Output ')' after traversing a right subtree

Generates the postfix expression ... 5 6 + 8 3 - *


Task 5.6
 Expression trees

Practice representing the following infix algebraic expressions as binary expression trees and use pre, in and postorder traversal to represent them in prefix, infix and postfix.

HINT : Start at the bottom of the tree by writing the operands in order. The work your way up the tree starting with the highest precedence operation until you get to the least precedence operation.
  • 6 + 9
  • 12 + (5 * 7)
  • (12 + 5) * 7
  • (8 * (2 / 9)) – 2
OUTCOME : Expression trees and pre, in and postfix expression generated from them using traversals.



Activity 6 Route / Path finding


The path finding algorithms we study at A Level are greedy algorithms - they make the best choice at any single given point and never look ahead or look behind to find a more efficient solution and therefore, even though they are generally fast, they do not always find the optimal solution. This is in contrast to dynamic programming solutions which, though slower, will consider the whole problem and refine the solution based on future detail (and are well outside the scope of A Level).


There are a number of so called standard 'Pathfinding algorithms' including the very well known Dijkstra's Algorithm and the related special case, the A* Algorithm which will shall study at this level.

Dijkstra's Algorithm

There are two parts to the simplest implementation of Dijkstra's Algorithm ...
a) the discovery of the shortest path from the starting vertex to all other vertices (stopping on the discovery of the destination vertex if we are searching for a particular path) and 
b) backtracking to find the shortest route from each vertex to the start.


Your teacher will demonstrate how to implement both parts of Dijkstra's Algorithm on the following graph ...

https://drive.google.com/file/d/0B83yXMOilskacVJIZ3A5S0hMTDQ/view?usp=drive_web
Click to enlarge and print a copy!

Task 6.1 Flipped learning

Your school should have a MyMaths subscription (if it doesn't, ask your maths teachers!). There is a series of simple lessons on Dijkstra's Algorithm in 'Decision 1' but you need to be able to log in with your schools username and password (not necessarily your personal one).

MyMaths > A Level > Decision 1 > Algorithms on Graphs > Dijkstra's Algorithm 1, 2 and 3

Work your way through the lesson, writing notes as you go. Reflect back on the demonstration your teacher showed you before this task - did it make it easier?

There is an information sheet on 'Dijkstra's Algorithm' for you to download to help you.

OUTCOME : Notes on Dijkstra's Algorithm



In the following Computerphile video, Dr Pound shows you a method of combining both methods into one using a priority queue. Use of a priority queue avoids the use of the 'backtracking' part of the Dijkstra's Algorithm we saw in the previous part of the lesson, therefore speeding up the process.

Dijkstra's Algorithm - Computerphile (10:42)

Task 6.2 Physical demonstration

Try to reconstruct Dr Pounds demonstration yourself and use it to find the shortest path from A through to G on the graph you used in the previous task. Show your teacher what you have done.

OUTCOME : Physical demonstration of Dijkstra's Algorithm using a priority queue (as per Dr Pound).


You've got to be kidding!

A* Algorithm

The A* algorithm is an extension of Dijkstra's Algorithm which implements simple heuristics in order to keep the search for the shortest path in generally the correct direction. Again, Dr Pound explains it much better than I could ever do, so, watch the video ...

A* (A Star) Search Algorithm - Computerphile (14:03)

Task 6.3 Create your own demonstration

I would like you to create your own demonstration and possibly a video / animation to show how the A* algorithm works in practice. Don't worry about implementing this yet (unless you want to of course, maybe for an A Level project?)

Demonstrate your demonstration (!) to your teacher / peers / parents / pets and see if they understand your explanation. I guess this is a bit like teaching it?


OUTCOME : A lesson on the A* algorithm, taught and evaluated.


You've got to be kidding!


Extension Activities 

How about these?
  • Download and complete the extra worksheet Graph traversal exercise from the lesson resources.

  • Read more about creating a binary search tree implementation at Kukuruku.

  • And another with a different approach using just one class for the node. After all, a binary tree is a node, isn't it?

  • Could you try to implement some of the applications of tree traversals? You will need to use either graph or binary tree abstract data structures depending on what you want to achieve and you might need to alter the structure of the vertex nodes to incorporate a 'data' attribute and then use this to store the information you will process like the component of the expression tree or the disk cost of a file. Great focus for project work!

  • You can also traverse a binary search tree breadth first though it is not as commonly used. Read the information on the following website and try to implement a breadth first binary search tree traversal algorithm yourself.

  • Depth first traversal of a tree can be used to find a (non-optimal) route through a perfect maze (no cycles or open spaces). Remember, however, that mazes are arbitrary trees, not binary trees. You represent them as graphs with no cycles, not binary trees. Click the maze to find out more.
    http://www.migapro.com/depth-first-search/
  • Visualise path finding algorithms using PathFinding.js!

  • One application of shortest path algorithms is in the field of maze solving. Use the following resources to research mazes and the implementation of their solution.

    - Dr Pound extends his treatment of shortest path algorithms to mazes on YouTube.
    - Dr Pounds implementation of his maze algorithms.
    Daedalus Maze Drawing program.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT