Summary: In this tutorial, we will learn what In-order Traversal is and how to implement In-order traversal to traverse a graph in C++ and Java.

Introduction to Inorder Traversal

A binary tree can be traversed in 2 major ways and they are:

Inorder traversal is a type of Depth-first traversal which traverse a graph in the following fashion:

  1. Left Subtree
  2. Root
  3. Right Subtree.

For example, consider the inorder traversal of the following graph:

inorder traversal
In-order Traversal

In this example, the algorithm visits the left node first i.e. B then the root node i.e. A, and finally the right node i.e. C.

Since In-order traversal is Depth First Search (because it explores depth along a branch), it can be implemented using a stack.

But the best way to implement an In-order traversal algorithm is using recursion because recursion implements stack and makes backtracking very easy.

Inorder Traversal Recursive Algorithm

  1. Inorder(leftChild)
  2. Output(currentNode)
  3. Inorder(rightChild)
inorder traversal in binary tree

Here is the implementation of the Inorder traversal algorithm in C++ and Java.

C++

Java

Output

inorder traversal in c++

Notice the output of the program, It is in ascending order.

It is because the Inorder traversal of a Binary Search Tree always yields the nodes in increasing order.

In our program, we have written the insert function in such a way that it forms a Binary Search Tree (In BST, a node have maximum 2 child nodes: left child node with a smaller value, and right child node with greater value).

In this tutorial, we learned what In-order traversal is and have also seen the implementation of In-order travseral to traverse a binary search tree in C++ and Java.

Leave a Reply