Inorder Traversal

Inorder Traversal: A binary tree can be traversed into 4 major ways and they are:

  • Inorder Traversal
  • Pre Order Traversal
  • Post Order Traversal
  • level first Traversal

We have already discussed level first traversal of a Binary search tree. In this tutorial, we will discuss in order traversal of a binary tree.

Inorder Traversal

In inorder traversal technique, we first visit left child node, then the root/parent node and then the right child node. Take a look at the picture below with three nodes and their inorder traversal output.

inorder traversal

Inorder Traversal Algorithm

The algorithm for inorder traversal is very simple an same as traversing the 3 nodes as stated above.

  1. Select the root of the tree.
  2. Check if it has any left child nodes. If yes then repeat this step (Step 2). Else go to step 3
  3. Print/output the node data.
  4. Check if it has any right child. If yes then repeat step 2 for the current node. Else print the node data.
  5. End.

inorder traversal in binary tree

Inorder Traversal code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
 
using namespace std;
 
//Class TreeNode represent each node
class TreeNode{
public:
    int data;
    TreeNode *leftNode {nullptr};
    TreeNode *rightNode {nullptr};
 
    TreeNode();
    TreeNode(int d);
    void insertData(int d);
    int getData();
    TreeNode* getLeftNode();
    TreeNode* getRightNode();
    void setLeftNode(TreeNode *node);
    void setRightNode(TreeNode *node);
    void display();
    void inorderTraverse();
};
 
//Implementing TreeNode class prototypes function.
TreeNode::TreeNode(int d){
    data = d;
}
 
 
int TreeNode::getData(){
    return data;
}
 
TreeNode* TreeNode::getLeftNode(){
    return leftNode;
}
 
TreeNode* TreeNode::getRightNode(){
    return rightNode;
}
 
void TreeNode::setRightNode(TreeNode *node){
    rightNode = node;
}
 
void TreeNode::setLeftNode(TreeNode *node){
    leftNode = node;
}
 
//Inserting node as left child if it is smaller than current node
//else it will be inserted as right child
// Assuming no two numbers/nodes are same
void TreeNode::insertData(int d){
    if(d < data){
        if(leftNode == nullptr){
            leftNode= new TreeNode(d);
        } else {
            leftNode->insertData(d);
        }
    } else {
        if(rightNode == nullptr){
            rightNode = new TreeNode(d);
        } else {
            rightNode->insertData(d);
        }
    }
}
 
//Implementinf inorder traversal algorithm in code
void TreeNode::inorderTraverse(){
    if(leftNode != nullptr){
        leftNode->inorderTraverse();
    }
 
    cout << data << ", ";
 
    if(rightNode != nullptr){
        rightNode->inorderTraverse();
    }
 
}
 
void TreeNode::display(){
    cout << "Data: "<< data << endl;
    //cout << "LeftNode " << this->leftNode << endl;
    //cout << "RightNode " << this->rightNode << endl;
}
 
 
int main()
{
    //Taking root node as 25
    TreeNode *root= new TreeNode(25);
 
    //inserting data into the binary tree
    root->insertData(20);
    root->insertData(23);
    root->insertData(31);
    root->insertData(36);
    root->insertData(19);
    root->insertData(26);
 
    //Calling inorder traversal function from root object
    root->inorderTraverse();
 
    return 0;
}

Output

inorder traversal in c++

Notice the output of this tree traversal c++ program. It is in ascending order. It is because inorder traversal in the binary tree gives output from the minimum value to maximum value.

Also in the code, we have inserted the node into such a way that it forms binary search tree (A node will have only 2 child nodes, left child node with smaller value and right child node with greater value).

That’s all for the inorder traversal of a binary tree in C++. If you have any doubt then comment below.

Leave a Reply

Close Menu