Back

Traversal of trees, depth 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 depth first here. The depth first approach simply means that you go deeper down into the tree before you start backtracking and checking siblings in the tree (sub-trees to one side of the sub-tree you are in). There are three approaches you can use. These are called in-order, pre-order and post-order.

Traversing binary trees and backtracking
When we want to visit a binary tree and look at its nodes, there are three different ways we can do this. These are known as

    • IN-ORDER
    • PRE-ORDER
    • POST-ORDER

Consider the following binary tree.

If you look at this tree, you should notice that there may be a tree structure under every node. For example, look at the node B. There is a tree structure with B as the root node and nodes underneath it. We can say that a tree may be made up of sub-trees and we can use this property (recursion) to traverse the tree in different ways. We are going to fully explore a sub-tree before backtracking and exploring other sub-trees. 

Traversing a tree: IN-ORDER
Using this method, we must visit the tree in this order:

    • Visit the left sub-tree.
    • Visit the root node.
    • Visit the right sub-tree.

How does this work? We visit the left sub-tree, then the node, then the right sub-tree.

    • We start at the root, node A.
    • Underneath node A is the left sub-tree (with root node B) and the right sub-tree (with root node C).
    • We must check the left sub-tree first according to our INORDER rules. Move to B.
    • But B has a left sub-tree (with a root at D) and a right sub-tree (with a root at E).
    • We must check the left sub-tree first according to our INORDER rules. Move to D.
    • D does not have a left sub-tree, so visit the node D.
    • Now check for D’s right sub-tree. It doesn’t have one.
    • We have now done the left sub-tree for the tree that has a root node at B. Now visit node B.
    • Now visit the right sub-tree of B. We move to E.
    • E doesn’t have a left sub-tree so visit E.
    • E doesn’t have a right sub-tree so move to B and because we have now completely visited the tree with the root node at B, we move up to node A. Visit node A.
    • Now visit the right sub-tree of A. We move to C.
    • C doesn’t have a left sub-tree so visit C.
    • C doesn’t have a right sub-tree so move back up to A.
    • We have now visited every node.

The order that we visited the nodes was DBEAC. We can write an algorithm to print out all of the data at the nodes, like this:

    1. For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 2. If there isn’t, go to 3.
    2. Repeat 1.
    3. Print the current node.
    4. For the current node, check whether it has a right sub-tree. If it has go to 5 else go to 6.
    5. Repeat 1.
    6. END

This algorithm will take a little bit of thinking about because it is a recursive algorithm. Refer back to chapter 10 on recursion. To understand this algorithm, you need to draw a box for each recursive call as we did in chapter 10.


  

Traversing a tree: PRE-ORDER
Using this method, we need to

    • Visit the root node.
    • Visit the left sub-tree.
    • Visit the right sub-tree.

Using our previous binary tree, we would visit the nodes in the order: A B D E C. We can write an algorithm that would print out all of the data at the nodes, like this:

    1. Print the current node.
    2. For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 1. If there isn’t, go to 3.
    3. For the current node, check whether it has a right sub-tree. If it has go to 4. else go to 5.
    4. Repeat 1.
    5. END.


 

Traversing a tree: POST-ORDER
Using this method, we need to

    • Visit the left sub-tree.
    • Visit the right sub-tree.
    • Visit the root node.

post

Using our example binary tree, the order that we would visit is: D E B C A

Back