3 Binary Tree Traversal Algorithm (Preorder, Inorder and Postorder)

The tree is an important data structure. It has a parent and children relationship at various levels.

In this article, we are more focusing on tree traversing. You will also learn different types of binary tree traversal algorithm.

What is a Binary Tree in Data Structure?

It is a special type of tree.

The binary tree is tree data structure which has at most two children for every node.

Here left and right children nodes are distinct.

In the above tree diagram, the node with value ‘4’ is the root node. It has two children nodes with the values ‘1’ and ‘3’.

This is another diagram and example where a binary tree is used to find the Fibonacci number series.

Don’t think about it right now. we will see the Fibonacci number series later as it is out of the scope of this article.

What is Tree Traversing?

In the tree, the address of the root node is only accessible to us. We can not access any other nodes directly.

If you want to visit any node, the only way is to travel the tree.

First, visit the root node, find their children nodes, then grandchildren nodes and so on…

To visit all the notes, there is a certain pattern is followed to visit all the nodes on the given tree. The type of flow or pattern used to visit the node in the tree is called the tree traversing algorithm.

Unlike other data structures such as an array, stack, queue, linked list; there are are many ways to traverse the elements of the binary tree. In this post, we see various types of binary tree traversal with its algorithm.

Different Types of Binary Tree Traversing Algorithm

There are 3 standard types of depth search binary tree traversal and one breath search binary tree traversal.

In this article, we are looking at the depth search level algorithm.

Let’s look at the different Depth Search Level order binary tree traversal one-by-one.

• Preorder binary tree traversal
• Inorder binary tree traversal
• Postorder binary tree traversal

Note: While going through different binary tree traversal algorithm, we will refer the following diagram as an example.

Traversing algorithms can be implemented using recursion technique or loop.

1. Preorder Binary Tree Traversal

The first node will be visited then it will traverse to left subtree and then right subtree.

Algorithm Preorder(tree)

Visit root node of the tree
call preorder(left subtree) //recursion call
call preorder(right subtree) //recursion call

Example: The preorder traversal of the above tree is 4 1 7 3 5 6.

Use of Preorder Traversal:

Preorder traversal can be used to find out the polish notation of the expression. Polish notation is useful to evaluate the expression effectively.

2. Inorder Binary Tree Traversal

The left subtree will be traversed first, then the root node will be visited.  After that, it will call to right subtree.

Algorithm Inorder(tree)

call inorder(left subtree) //recursion call
Visit the root node of the tree
call inorder(right subtree) // recursion call

Example: If we find the inorder traversal of the above tree, it will be 7 1 3 4 5 6.

Use of inorder traversal:

If we apply the inorder traversal on binary search tree it will give numbers in ascending order. So the inorder traversal is used to find the numbers in increasing order for binary search tree.

3. Postorder Binary Tree Traversal

The left subtree and then the right subtree will be traversed first. After that, the root node will be visited.

Algorithm Postorder(tree)

call postorder(left subtree) // recursion call
call postorder(right subtree) // recursion call
Visit the root node of the tree

Example: The postorder traversal of the above tree is 7 3 1 6 5 4.

Use of postorder traversal:

It is used to find out postfix expression. It is also useful for deleting nodes in the linked list. As elements at the bottom get deleted first, the structure of the tree after deletion of the bottom node will get preserved.

Python Code for Binary Tree Traversal

class node:
def __init__(self, val, left=None, right=None):
self.left=left
self.val=val
self.right=right

def traverseInOrder(root):
if root:
traverseInOrder(root.left)
print(root.val)
traverseInOrder(root.right)

def traversePreOrder(root):
if root:
print(root.val)
traversePreOrder(root.left)
traversePreOrder(root.right)

def traversePostOrder(root):
if root:
traversePostOrder(root.left)
traversePostOrder(root.right)
print(root.val)

root=node(4)
root.left=node(1)
root.right=node(5)
root.left.left=node(7)
root.left.right=node(3)
root.right.right=node(6)

print("Preorder Traversal of Binary Tree:")
traversePreOrder(root)
print("Preorder Traversal of Binary Tree:")
traverseInOrder(root)
print("Preorder Traversal of Binary Tree:")
traversePostOrder(root)

Output:

Preorder Traversal of Binary Tree:
4
1
7
3
5
6
Preorder Traversal of Binary Tree:
7
1
3
4
5
6
Preorder Traversal of Binary Tree:
7
3
1
6
5
4

Wrapping up…

The binary tree traversal algorithm is also used in the min-max heap data structure.

I see a lot of questions related to the tree traversing asked in many of the interviews. So, understand it very well.

If you have any questions related to Preorder, inorder and postorder depth-first search traversal, write a comment below.

Aniruddha Chaudhari

I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on <b>CSEstack.org</b> portal.