[Tree traversal](https://www.educative.io/answers/what-is-tree-traversal) happens when all the nodes of a tree are visited only once. Trees can be traversed in multiple ways, one such way is **in-order** traversal. In-order traversal is mainly used to print the values, stored in the nodes of a [binary search tree](https://www.educative.io/answers/what-is-a-binary-search-tree), in ascending order.

<br>

# Basic algorithm

The algorithm below is specific to a [binary tree](https://www.educative.io/answers/what-is-a-binary-tree), but it can be generalized into an n-ary tree (a tree where each node can have, at most, n children nodes).

1. Recursively traverse the left subtree.
2. Visit the root.
3. Recursively traverse the right subtree.

For an n-ary tree:

1. Traverse the leftmost​ subtree.
2. Visit the root node.
3. Traverse the remaining subtrees (going from left to right).

# Implementation in C++

The following code snippet implements in-order traversal for a binary tree.

#include <iostream>
using namespace std;

struct Tree
{
	char data;
	Tree *left;
	Tree *right;
  Tree(char data) 
    { 
        this -> data = data; 
        left = NULL;
        right = NULL; 
    }     
};
void InOrderTraversal(Tree *node)
{
	if(node == NULL){
    return;
  }
  else{
    InOrderTraversal(node -> left);
    cout << node -> data << ", ";
    InOrderTraversal(node -> right);
  } 
}
int main() {
  Tree *root = new Tree('a'); 
  root -> left = new Tree('b'); 
  root -> right = new Tree('c'); 
  root -> left -> left = new Tree('d'); 
  root -> left -> left -> left = new Tree('e');
  root -> left -> left -> right = new Tree('f');  
  InOrderTraversal(root);
  return 0;
}

What is in-order traversal?

Tree traversal happens when all the nodes of a tree are visited only once. Trees can be traversed in multiple ways, one such way is in-order traversal. In-order traversal is mainly used to print the values, stored in the nodes of a binary search tree, in ascending order.  Basic algorithm The algorithm below is specific to a binary tree, but it can be generalized into an n-ary tree (a tree where each node can have, at most, n children nodes).  Recursively traverse the left subtree. Visit the root. Recursively traverse the right subtree.  