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
Copyright ©2022 Educative, Inc. All rights reserved

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.

Keep Exploring