A Tree is a non-linear data structure that is normally used to represent hierarchical data.

In non-linear data structures, elements do not have a simple next-previous relationship like in arrays or linked lists. Thus to traverse through the elements in a tree,  we need to use specialized algorithms.

Consider if we have a tree structure like one shown below:

Example of a tree

Tree traversal refers to  the process of visiting every node in a tree exactly once. There are various important  types of tree traversal algorithms, they includes:

  1. Breadth-First Traversal
  2. Pre-Order Traversal
  3. Post-Order Traversal

Before we look at the traversal algorithms we will first need to be able to implement trees.

In this article we will use the treelib package to represent trees and nodes. This package does not exist in the standard library, it can be installed using the following pip command.

pip install treelib

creating a tree

#import the Tree class
from treelib import Tree

#create a tree object
T = Tree()

#add nodes.
T.create_node(data = 0, identifier = '0')
T.create_node(data =1, identifier = '1', parent = '0')
T.create_node(data = 2, identifier = '2', parent = '0')
T.create_node(data = 3, identifier = '3', parent = '1')
T.create_node(data = 4, identifier = '4', parent = '1')
T.create_node(data = 5, identifier = '5', parent = '2')
T.create_node(data = 6, identifier = '6', parent = '2')
T.create_node(data = 7, identifier = '7', parent = '3')
T.create_node(data = 8, identifier = '8', parent = '3')
T.create_node(data = 9, identifier = '9', parent = '4')

#display the tree
print(T)

The create_node() method of tree creates a new node and links it to the relevant existing nodes. It has the following syntax:

T.create_node(tag = None, identifier = None, parent = None, data = None)
tag A human readable representation of the node. It defaults to None.
identifier A unique identifier of a node in the tree. If not given, a unique random identifier is auto-generated.
parent The identifier of this node's parent node.
data The value stored by the node.

In addition to the create_node() method, we will also use the following method of treelib.Tree objects when implementing the traversal algorithms.

T.get_node(identifier) Returns the node whose identifier is given as argument. Raises an exception if no such node exists.
T.children(identifier) Returns a list containing all children of the node whose identifier is given as argument.

Breadth-first Traversal

Breadth-First traversal is also referred to as Level-Order traversal. This is the easiest traversal mode to understand but it is slightly hard to implement compared to the rest.

In breadth-first traversal, the nodes are visited Level-by-Level, starting from the root node. At each level, the nodes are visited starting from the leftmost node going to the rightmost node.

levels in a tree

With breadth-first traversal, the nodes in the above tree would be visited in the following sequence:

0,1, 2, 3, 4, 5, 6, 7, 8, 9

Implement breadth-first traversal

The breadth-first traversal algorithm can be implemented by following the steps outlined below:

  1. Create an empty queue.
  2. Enqueue the root node into the queue.
  3. While the queue is not empty, do the following steps:
    • Dequeue a node from the queue.
    • process the node. e.g display it.
    • Get all the children nodes of the dequeued node.
    • For each child node, enqueue it into the queue.
  4. Once the queue is empty, the traversal is complete. 

Enqueue and dequeue operations are used to add and remove an element from a queue, respectively. Enqueue operation adds an element at the back of the queue while dequeue operation removes the element at the front of the queue.

The dequeue (pronounced  "dee-kew") operation should not be confused with deque(pronounced as "deck") which is a data structure  that represent a double-ended queue.

In our implementation of breadth_first(), we will use collections.deque object as a queue. We will enqueue an element by adding it at the back of the deque using deque.append() method, the deque.popleft() will be used to perform a dequeue operation.

Implement breadth_first()

#import the deque class
from collections import deque

def breadth_first(T):
    
    #create an empty queue
    Q = deque()
    Q.append(T.get_node(T.root)) #enqueue root node

    while len(Q) > 0:
        current = Q.popleft() #dequeue the front node
        print(current.data)
        for child in T.children(current.identifier):
            Q.append(child)

 Using breadth_first() 

#import the Tree class
from treelib import Tree
from collections import deque

#create a tree object
T = Tree()

#add nodes.
T.create_node(data = 0, identifier = '0')
T.create_node(data =1, identifier = '1', parent = '0')
T.create_node(data = 2, identifier = '2', parent = '0')
T.create_node(data = 3, identifier = '3', parent = '1')
T.create_node(data = 4, identifier = '4', parent = '1')
T.create_node(data = 5, identifier = '5', parent = '2')
T.create_node(data = 6, identifier = '6', parent = '2')
T.create_node(data = 7, identifier = '7', parent = '3')
T.create_node(data = 8, identifier = '8', parent = '3')
T.create_node(data = 9, identifier = '9', parent = '4')

breadth_first(T) #Implementation of breadth_first() function is omitted, refer to the previous section

0
├── 1
│   ├── 3
│   │   ├── 7
│   │   └── 8
│   └── 4
│       └── 9
└── 2
    ├── 5
    └── 6

Breadth-first:
0
1
2
3
4
5
6
7
8
9

Pre-order Traversal

In Pre-order traversal, we start by visiting the root node, then recursively traverse the subtrees rooted at the children of the root.

Consider our example tree shown below:

tree for pre-order traversal

With pre-order traversal for the entire tree, the nodes will be visited in the following order.

0, 1, 3, 7, 8, 4, 9, 2, 5, 6

One important aspect of the pre-order traversal is that it can be performed for a subtree instead of the entire tree. For example, the pre-order traversal of node "1" above, will yield:

1, 3, 7, 8, 4, 9

The pre-order algorithm can be implemented recursively through the following steps:

  1. Visit the root node.
  2. Recursively visit all sub-trees rooted on the children of the root.
def pre_order(T, nid):
    print(T.get_node(nid).data)
    for child in T.children(nid):
        pre_order(T, child.identifier)

#nid refers to "node identifier"

In the above example, the pre_order()  method takes in two arguments, the tree and nid, which is the identifier of the node whose subtree is to be traversed in pre-order.

pre_order() for entire tree

#import the Tree class
from treelib import Tree

#create a tree object
T = Tree()

#add nodes.
T.create_node(data = 0, identifier = '0')
T.create_node(data =1, identifier = '1', parent = '0')
T.create_node(data = 2, identifier = '2', parent = '0')
T.create_node(data = 3, identifier = '3', parent = '1')
T.create_node(data = 4, identifier = '4', parent = '1')
T.create_node(data = 5, identifier = '5', parent = '2')
T.create_node(data = 6, identifier = '6', parent = '2')
T.create_node(data = 7, identifier = '7', parent = '3')
T.create_node(data = 8, identifier = '8', parent = '3')
T.create_node(data = 9, identifier = '9', parent = '4')

print(T)
print("Pre-order:")
pre_order(T, T.root) #Implementation of pre_order() function is omitted, refer to the previous section

0
├── 1
│   ├── 3
│   │   ├── 7
│   │   └── 8
│   └── 4
│       └── 9
└── 2
    ├── 5
    └── 6

Pre-order:
0
1
3
7
8
4
9
2
5
6

pre-order() for a subtree

#import the Tree class
from treelib import Tree

#create a tree object
T = Tree()

#add nodes.
T.create_node(data = 0, identifier = '0')
T.create_node(data =1, identifier = '1', parent = '0')
T.create_node(data = 2, identifier = '2', parent = '0')
T.create_node(data = 3, identifier = '3', parent = '1')
T.create_node(data = 4, identifier = '4', parent = '1')
T.create_node(data = 5, identifier = '5', parent = '2')
T.create_node(data = 6, identifier = '6', parent = '2')
T.create_node(data = 7, identifier = '7', parent = '3')
T.create_node(data = 8, identifier = '8', parent = '3')
T.create_node(data = 9, identifier = '9', parent = '4')

print(T)
print("Pre-order for node '1':")
pre_order(T, '1') #Implementation of pre_order() function is omitted, refer to the previous section

0
├── 1
│   ├── 3
│   │   ├── 7
│   │   └── 8
│   └── 4
│       └── 9
└── 2
    ├── 5
    └── 6

Pre-order for node '1':
1
3
7
8
4
9

Post-order Traversal

Post-order traversal can be thought of as the opposite of the pre-order traversal. In this mode, the left subtree and the right subtree are visited before the root, hence the name "post-order".

The traversal follows the order left -> right  -> root

Consider our demo tree below;

tree for post-order traversal

With post-order traversal the nodes will be visited in the following order:

7, 8, 3, 9, 4, 1, 5, 6, 2, 0,

Similar to pre-order, post-order traversal can be performed on the subtree rooted at a specific node instead of the entire tree.

The post-order algorithm can be implemented recursively through the following steps:

  1. Recursively visit the children of the root node.
  2. Visit the root node.

 Note that the above steps are just like in pre-order, but reversed.

implement post_order()

def post_order(T, nid):

    for child in T.children(nid):
        post_order(T, child.identifier)
    print(T.get_node(nid).data)

post_order() for entire tree

#import the Tree class
from treelib import Tree

#create a tree object
T = Tree()

#add nodes.
T.create_node(data = 0, identifier = '0')
T.create_node(data =1, identifier = '1', parent = '0')
T.create_node(data = 2, identifier = '2', parent = '0')
T.create_node(data = 3, identifier = '3', parent = '1')
T.create_node(data = 4, identifier = '4', parent = '1')
T.create_node(data = 5, identifier = '5', parent = '2')
T.create_node(data = 6, identifier = '6', parent = '2')
T.create_node(data = 7, identifier = '7', parent = '3')
T.create_node(data = 8, identifier = '8', parent = '3')
T.create_node(data = 9, identifier = '9', parent = '4')

print(T)
print("Post-order:"
post_order(T, T.root) #Implementation of post_order() function is omitted, refer to the previous section

0
├── 1
│   ├── 3
│   │   ├── 7
│   │   └── 8
│   └── 4
│       └── 9
└── 2
    ├── 5
    └── 6

Post-order:
7
8
3
9
4
1
5
6
2
0

Use another node instead of root to perform post-order traversal for the subtree rooted at that node.

Conclusion

The modes of tree traversal  that we have looked at above are applicable to all type of trees. There are other modes that are only applicable to specific type of trees. One such example is the in-order traversal that can only be applied to a binary tree.