Traversal of trees breadth first
Introduction
There are a number of ways that we can search through a tree to find what we want. Broadly, they split into two approaches, depth first and breadth first. We will consider breadth first here.
Traversing binary trees using beadth first
Consider the following binary tree:
The element in the tree is at a certain level (or depth) from the root node H. Programmers like to start counting at zero, so the root is at level 0. Elements C and B are at level 1. D, T and N are at level 2 and element E is at level 3. if we want to visit the elements depth first rather than using one of the depth first methods, we would visit them starting at level 0 and going left to right, then level 1 and going left to right, then level 2 going left to right and finally level 3 going left to right. We would visit the nodes (the elements) in this order:
H C B D T N E
Why would you need beadth first traversal?
There are many situations where data is organised in levels rather than in depth. If you think of a school, with the Head in charge of everyone. To help him, he may have two Deputy Heads. The Deputy Heads will have some Senior Managers to help them as part of the Senior Management Team (SMT). Some of the Senior Managers are the line manager for some Departmental Heads. The Departmental Heads will be in charge of teachers, technicians and so on. We could represent this using a simple tree structure:
If we needed to know who was on the same management level, we would access the tree using a breadth first algorithm. This would allow us to print off:
Headteacher
Deputy Head 1
Deputy Head 2
SMT 1
SMT 2
SMT 3
SMT 4
SMT 5
SMT 6
Depart 1
Depart 2
Depart 3
Depart 4
Depart 5
Depart 6
Depart 7
Many organisations are structured in this way. A family tree is also structured like this. If you want to print off all the brothers and sisters, all the cousins, all the grandfathers, you would use breadth first to go through the tree. When games are played, a player often has a number of possible moves. Some are better than others so a breadth first approach may be appropriate in some circumstances. for example, when playing chess, you may be able to move your queen to a place where it can be taken. This is usually a bad move but do you really want to explore all the moves after having your queen taken (a feth first approach) or would it be better to explore moves that don't involve having your most important piece taken (a breadth first approach)?
Breadth first or depth first?
Breadth first traversal uses much more memory than a depth first traversal because with breadth first, you have to store all the child nodes' pointers at each level. Which one you use, however, really comes down to what data you want to find, what the purpose of your traversal or search is. If you had a family tree and you were looking for the youngest member of the family, they would be at the bottom of the tree in all likelihood. To reach the bottom with breadth first traversal, however, is going to take much longer compared to depth first traversal. On the other hand, if you wanted to find someone who died a long time ago, then breadth traversal will allow you to quickly look-up and examine all of the earliest members of the family.
A breadth first algorithm
When you traverse a tree using breadth first, you start at the root node (level 0) and visit each of the root node's child nodes first (the elements in level 1) starting on the left. Then you go down a level to level 2 and starting on the left, visit each of those nodes, and continue this until there are no more nodes to visit. There are a number of ways of implementing a breadth first traversal. The simplest way is to use a queue. In queues, a new data item is added at the back of other data items already in the queue, and items in the queue are always removed from the front. We need to have a picture of this in our heads:
1. Create an empty queue called Q
2. v = root
3. Visit v
4. Add v to Q
5. WHILE (Q is not empty) DO:
6. Take out v from Q
7. FOR (each child u of v)
8. Visit u
9. Add u to Q
10. END FOR
11. END WHILE
To see this working, you need to trace an example like the one we saw at the start:
1. Create an empty queue called Q.
2. H is the root.
3. Visit H
4. Add H to Q
5. Q is not empty = TRUE
6. Remove H from Q
8 + 9. Visit C and add C to Q
8 + 9. Visit B then add B to Q
5. Q is not empty = TRUE (The queue now holds BC, with C at the front of the queue and B at the back.)
6. Remove C from Q
8 + 9. Visit D and add D to Q
8 + 9. Visit T and add T to the Q
5. Q is not empty = TRUE (The queue now holds TDB, with B at the front of the queue and T at the back.)
6. Remove B from Q
8 + 9. Visit N and add N to Q
5. Q is not empty = TRUE (The queue now holds NTD, with D at the front of the queue and N at the back.)
6. Remove D from Q
8 + 9. Visit E and add E to Q
5. Q is not empty = TRUE (The queue now holds ENT, with T at the front of the queue and E at the back.)
6. Remove T from Q
5. Q is not empty = TRUE (The queue now holds EN, with N at the front of the queue and E at the back.)
6. Remove N from Q
5. Q is not empty = TRUE (The queue now holds E, with E at the front of the queue and E at the back.)
6. Remove E from Q
5. Q is not empty = FALSE (The queue is now empty, so 'not empty' is FALSE.)
END