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 the in-order traversal of a binary tree.
Inorder Traversal
In the inorder traversal technique, we first visit the 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 Algorithm
The algorithm for inorder traversal is very simple an same as traversing the 3 nodes as stated above.
- Select the root of the tree.
- Check if it has any left child nodes. If yes then repeat this step (Step 2). Else go to step 3
- Print/output the node data.
- Check if it has any right child. If yes then repeat step 2 for the current node. Else print the node data.
- End.
Inorder Traversal code
C++
|
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 |
#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); void inorderTraverse(); }; //Implementing TreeNode class prototypes function. TreeNode::TreeNode(int d){ data = d; } //Inserting node as a left child if it is smaller than the current node //else it will be inserted as the 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(); } } 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; } |
Java
|
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 |
class Node{ int value; Node left; Node right; //Constructor to initialize value to node Node(int value){ this.value = value; left = right = null; } //Function to insert data i.e to form binary tree public void insert(int v){ if(v < value){ if(left == null){ left = new Node(v); } else { left.insert(v); } } else { if(right == null){ right = new Node(v); } else{ right.insert(v); } } } //Function to perform In Order Travesal public void inOrder(){ if(left != null){ left.inOrder(); } System.out.print(value+" "); if(right != null){ right.inOrder(); } } } class Main { public static void main(String[] args) { Node root = new Node(25); root.insert(20); root.insert(31); root.insert(19); root.insert(23); root.insert(26); root.insert(36); root.inOrder(); } } |
Output
Notice the output of this tree traversal c++ program. It is in ascending order. It is because In-order traversal in the binary tree gives output from the minimum value to the 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++ and Java. If you have any doubt then comment below.