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. 🎉