For a video version:

This is an extension of the last article on Data Structures and Algorithms: Graph Traversals. In our last post on Graph Traversals we covered how to iteratively do Breadth First Search (BFS) and Depth First Search (DFS) on a graph with an adjacency list representation. In this article, we’re going to cover the recursive implementation of the three sub-algorithms for Depth First Search – inorder, preorder, and postorder traversals. If you’re scared of recursion, you won’t be after you see how simple these implementations are.

For this tutorial we’re not going to use an adjacency list representation, we’re going to use a class to create a custom Node object to make up our binary tree. For more information on classes check out our Introduction to Python Classes. We don’t need to install any packages for this so let’s go ahead and get started.

The first thing we need to do is create a Node class. Our Node class will have a constructor that takes a value. The value will be the value of the Node. Our Node class will also be instantiated with a left and right attribute that will be the left and right Nodes.

# create the node class - trees are just a bunch of linked nodes
class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

Now that we have a custom Node class, let’s make our tree. It doesn’t really matter if you use these numbers, but I’ve decided to start with a root with a value of 15. By convention, the value of the left node should be lower than the value of the root and the value of the right node should be higher.

root = Node(15)
root.left = Node(10)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(11)
root.right.left = Node(18)
root.right.right = Node(33)
root.left.left.right = Node(8)

This is what our tree looks like:

Example Tree for Recursive Tree Traversals

Alright now that we have a tree set up let’s go over how to do our recursive traversals

Recursive Python Preorder Tree Traversal

A preorder traversal is a Depth First Search traversal in which we process the current node before processing either the left or right node. As I said earlier, there’s no need to be afraid of recursion, it’s super simple really. All we do in this recursive implementation is check if the passed in node exists, and if it does, we process the node (print it’s value) and then call preorder on the left then right values. We check for existence first because when we created our Node class, the left and right nodes are automatically set to none.

# preorder implementation - the current node is processed first
def preorder(node):
    if node:
        print(node.value)
        preorder(node.left)
        preorder(node.right)
 
print("Preorder Traversal:")
preorder(root)

Our preorder traversal should look like this:

Preorder Recursive Tree Traversal Output

Recursive Python Inorder Tree Traversal

An inorder traversal is a DFS traversal where we process the current node in between the left and right nodes. Just like the preorder traversal above, we start by checking that the passed in node exists. If it does, we call inorder on the left node, process (print) the current node, and then inorder on the right node.

# inorder implementation - the current node is processed in between the left and right nodes
def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)
 
print("Inorder Traversal:")
inorder(root)

Our inorder traversal should look like this:

Since our tree is actually set up correctly, an inorder traversal should print the values in increasing order (the leftmost values are the smallest and they’re processed first, the rightmost values are the largest and they’re processed last)

Recursive Python Postorder Tree Traversal

A postorder traversal is a DFS traversal where we process the parent node after processing the left and right nodes. Just like the inorder and preorder traversals we first check that our node exists. If it does then we call postorder on the left node, then on the right node, and finally process our current node.

# postorder implementation - the current node is processed last
def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value)
 
print("Postorder Traversal:")
postorder(root)

Our postorder traversal should look like this:

Postorder Recursive Tree Traversal Output

That’s all there is to these recursive implementations of the tree main Depth First Search tree traversals. To learn more feel free to reach out to me @yujian_tang on Twitter, follow the blog, or join our Discord.

Recursive Python Preorder Tree Traversal

Recursive Python Inorder Tree Traversal

Recursive Python Postorder Tree Traversal

Further Reading

Share this: