Data Structures and Algorithms: Recursive Tree Traversals

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:

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:

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:

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.

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang
Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
%d bloggers like this: