Home

 › 

Articles

 › 

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

What Are Tree Traversals?

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:

What Are Tree Traversals?
An illustration of a tree structure.

©History-Computer.com

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:

What Are Tree Traversals?
Algorithm for the preOrder Traversal of a tree structure.

©History-Computer.com

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:

Traversals
Algorithm for the inOrder Traversal of a tree structure.

©History-Computer.com

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:

What Are Tree Traversals?

Al

gorithm for the postOrder Traversal of a tree structure.

©History-Computer.com

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. 

Frequently Asked Questions

What is a data structure?

Data structures are the specific formats used to organize data so it can be securely stored and efficiently managed and accessed. 

What are the main types of trees?

Apart from binary trees, the main types of trees include:

  • Heap trees
  • Syntax trees
  • Tries 
  • B-trees 
  • T-trees

 

What is a perfect binary tree?

A perfect binary tree has all leaf nodes at the same depth and all parent nodes have two children. This is another way of describing a completely filled, gap-free tree.

What are examples of non-tree data structures?

Non-tree data structures are mainly linear data structures that include:

  • Arrays
  • A bitmap
  • Matrix
  • Parallel array
  • Doubly linked list
  • Self-organizing list

What are abstract data types?

 Abstract data types (ADT) are mathematical models that can be used to structure data and facilitate large-scale programming. In computer science, ADTs can be used to package and manage data for a variety of computing applications.

To top