Tree Traversal Algorithms in Python

The tree data structure that we will be traversing is as shown below: A Tree Data Structure

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