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
right attribute that will be the left and right
# 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.
- Prim’s Algorithm in Python
- Underscores and Double Underscores in Python
- NLP Stop Words with spaCy and NLTK
- A Comprehensive Guide to the Random Library
- Build Your Own Content Moderator with Python and NLP
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.
Make a one-time donation
Make a monthly donation
Make a yearly donation
Choose an amount
Or enter a custom amount
Your contribution is appreciated.
Your contribution is appreciated.
Your contribution is appreciated.DonateDonate monthlyDonate yearly