Traversing Tree in Inorder Sequence Using C++

What is Tree?

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

What is Tree Traversal?

In computer science, tree traversal is a form of graph traversal that refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

What is Inorder Traversal?

When the root node is visited in middle of left subtree and right subtree then it is called Inorder Traversal. It is also called LNR traversal. LNR sequentially means Left Subtree, Node, Right Subtree. For each node the LNR sequence is followed in inorder traversal.

Steps of Inorder Traversal

1. Traverse the left subtree by recursively calling the in-order function. (8th line on code)
2. Access the data part of the current node. (9th line on code)
3. Traverse the right subtree by recursively calling the in-order function. (10th line on code)

Uses of Inorder Traversal

In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.

Example

In the above tree the inorder (yellow bubble) sequence is: A, B, C, D, E, F, G, H, I

C++ Code

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void PrintInorder(int Nodes[],int start,int end){
   if(start>end)
      return;
   PrintInorder(Nodes,start*2+1,end);   //Executing the left subtree
   cout<<Nodes[start]<<" ";             //Printing present value
   PrintInorder(Nodes,start*2+2,end);   //Executing the right subtree
}
int main(){
  int Tree[] = {4, 2, 6, 1, 3, 5, 7};
  int n = sizeof(Tree)/sizeof(int);
  cout<<"The Inorder Traversal is:"<<endl;
  PrintInorder(Tree,0,n-1);
  return 0;
}

Hope you like the tutorial. Please comment if you are satisfied. Follow the blog for getting update first.