What Are Tree Traversals (Inorder, Preorder, and Postorder) – With Examples

In computer science, data can be structured and traversed in a variety of ways. Binary trees are a form of hierarchical data storage that uses tree traversals as the primary method of visiting all the constituent nodes for searching, sorting, and other purposes. Understanding the various methods used for tree traversals can help you complete basic operations on a binary tree. In this article, we explain what tree traversals are including inorder, preorder, and postorder traversals, with examples to help you get started.

What are tree traversals?

Tree traversals are the methods computer scientists, developers, and software engineers use to traverse a binary tree. It is also known as:

• Walking the tree 
• Tree search 

These methods involve sequentially visiting each node within the binary tree. In contrast to a linear data structure like a linked list or queue, these traversals can be completed in a variety of ways. The main methods, explained below, are used for updating, deleting, searching, sorting, and retrieving data efficiently. 

About binary trees

Binary trees are the most commonly used form of tree which is a hierarchical data structure composed of interconnected nodes. Each node consists of left and right references and a data element. Each node in a binary tree is connected to one parent, but each parent node can only have a maximum of 2 children. Nodes with no children are called leaves. Nodes that share a parent node are called siblings. The node at the top of a binary tree is called the root. 

If a binary tree is completely filled it is called a complete tree. Trees are filled with nodes from left to right. You can position nodes by their height, which is the number of edges between the root and the index node, or their depth, which is the number of edges between the node and the farthest leaf node. 

Use Tree Traversals to Visit Every Node in a Tree

An important feature of these traversals is that every node in the tree is visited. Because trees are non-linear data structures, there are many ways and orders in which you can ensure that each node is visited in turn. There is no single traversal, but several traversal algorithms that you can work with. 

Tree Traversals are Important 

Mastering tree traversals is a key skill for organizing and working with data. This is because trees are an extremely common data structure and are widely used because of their clear representation of data relationships and hierarchies. 

You can use these traversal methods and examples for more efficient data searches or insertions. Let’s take a look at the key methods below:

Here is an example tree:

1. PreOrder Traversal 

This is a type of depth-first traversal where the parent node is visited first, then the left child node, and then the right child node. If a tree is traversed using the preOrder method, the root node is visited first then sequential left and right subtrees parent-first until the entire tree is traversed. PreOrder traversal provides an efficient method for copying a tree.

Here is the example preOrder traversal for the above tree: A > B >  D >  E > C  >  F > G

And here is the preOrder algorithm:

2. InOrder traversal

This is a type of depth-first traversal where the left child node is visited, then the parent, then the right child node. InOrder traversals proceed via the farthest left subtree and end at the farthest right subtree. This type of traversal produces data organized in ascending order. 

Here is the example inOrder traversal for the above tree: D > B >  E > A > F > C > G

And here is the inOrder algorithm:

3. PostOrder traversal

This third type of depth-first traversal visits the left child node, then the right child node then the parent. With postOrder tree traversal, the sub-trees are all visited first (from the lowest left) with the root visited last. PostOrder traversal is an efficient way to delete a tree. 

Here is the example postOrder traversal for the above tree: D >  E  >  B >  F >  G >  C > A

And here is the postOrder algorithm:

There is also a breadth-first traversal that visits nodes from top to bottom and left to right. This is the only form of breadth-first traversal.

Rounding up

As you can see tree traversals make the management of hierarchical data very simple. The algorithms are straightforward and if you lose your way, you can draw out a basic tree to orient yourself. These methods are so efficient that you can construct full binary trees from provided pre- and post-order traversals. Practice these methods to master them and extend your knowledge. 

The image featured at the top of this post is ©NicoElNino/Shutterstock.com.