Trusted answers to developer questions
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.
1 of 10
For an n-ary tree:
- Traverse the leftmost​ subtree.
- Visit the root node.
- 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 ©2024 Educative, Inc. All rights reserved
TRENDING TOPICS
Did you find this helpful?