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:

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)

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

## Java

Output

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.