# 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 `Node`s.

``````# 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.

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.

One-Time
Monthly
Yearly

#### 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

\$