The tree data structure that we will be traversing is as shown below:

You first need to represent the tree data structure. We will use a class that will be a template of all the nodes that we will need:
1
2
3
4
5
6
|
#define the Node class
class Node:
def __init__(self, root):
self.root = root
self.right = None
self.left = None
|
Next, we will need to initialize and connect the nodes to form a tree as shown in the figure above:
1
2
3
4
5
6
7
8
9
10
11
12
|
#initialise nodes
root = Node("1")
node1 = Node("2")
node2 = Node("3")
node3 = Node("4")
node4 = Node("5")
#connect the nodes
root.left = node1
root.right = node4
node1.left = node2
node1.right = node3
|
We are now ready to implement any of the tree traversal algorithms.
Pre Order Traversal
1
2
3
4
5
6
7
8
|
#the pre_order function, that is, it returns starting from the root, then left, then right
def pre_order(root, nodes):
nodes.append(root.root)
if (root and root.left):
pre_order(root.left, nodes)
if (root and root.right):
pre_order(root.right, nodes)
return nodes
|
In Order Traversal
1
2
3
4
5
6
7
8
|
#the in_order function, returns the left, then root, then right
def in_order(root, nodes):
if (root and root.left):
in_order(root.left, nodes)
nodes.append(root.root)
if (root and root.right):
in_order(root.right, nodes)
return nodes
|
Post Order Traversal
1
2
3
4
5
6
7
8
|
#the post_order function returns the left, the right then the root
def post_order(root, nodes):
if (root and root.left):
post_order(root.left, nodes)
if (root and root.right):
post_order(root.right, nodes)
nodes.append(root.root)
return nodes
|
Calling the various functions
1
2
3
4
5
6
7
8
|
result = pre_order(root, [])
print("Pre order: "+ str(result))
result = in_order(root, [])
print("In order: "+ str(result))
result = post_order(root, [])
print("Post order: "+ str(result))
|
The complete tree traversal algorithms code in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#define the Node class
class Node:
def __init__(self, root):
self.root = root
self.right = None
self.left = None
#initialise nodes
root = Node("1")
node1 = Node("2")
node2 = Node("3")
node3 = Node("4")
node4 = Node("5")
#connect the nodes
root.left = node1
root.right = node4
node1.left = node2
node1.right = node3
#the pre_order function, that is, it returns starting from the root, then left, then right
def pre_order(root, nodes):
nodes.append(root.root)
if (root and root.left):
pre_order(root.left, nodes)
if (root and root.right):
pre_order(root.right, nodes)
return nodes
#the in_order function, returns the left, then root, then right
def in_order(root, nodes):
if (root and root.left):
in_order(root.left, nodes)
nodes.append(root.root)
if (root and root.right):
in_order(root.right, nodes)
return nodes
#the post_order function returns the left, the right then the root
def post_order(root, nodes):
if (root and root.left):
post_order(root.left, nodes)
if (root and root.right):
post_order(root.right, nodes)
nodes.append(root.root)
return nodes
result = pre_order(root, [])
print("Pre order: "+ str(result))
result = in_order(root, [])
print("In order: "+ str(result))
result = post_order(root, [])
print("Post order: "+ str(result))
|
The output:
[Running] python -u "/Volumes/MAC/d/Algorithms/tree_traversal.py"
Pre order: ['1', '2', '3', '4', '5']
In order: ['3', '2', '4', '1', '5']
Post order: ['3', '4', '2', '5', '1']
[Done] exited with code=0 in 0.236 seconds
Thank you for reading. Feel free to contact me if you have any question, comment or suggestion.
🎉