Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structure
tree
traversal

# What is in-order traversal? Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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).

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

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).
1 of 15

## 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;}

RELATED TAGS

data structure
tree
traversal 