Inorder Traversal

In this article, we will discuss the inorder traversal in data structure.

If we want to traverse the nodes in ascending order, then we use the inorder traversal. Following are the steps required for the inorder traversal:

• Visit all the nodes in the left subtree
• Visit the root node
• Visit all the nodes in the right subtree

Linear data structures such as stack, array, queue, etc., only have one way to traverse the data. But in hierarchical data structures such as tree, there are multiple ways to traverse the data. Here we will discuss another way to traverse the tree data structure, i.e., inorder traversal.

There are two approaches used for the inorder traversal:

• Inorder traversal using Recursion
• Inorder traversal using an Iterative method

An inorder traversal technique follows the Left Root Right policy. Here, Left Root Right means that the left subtree of the root node is traversed first, then the root node, and then the right subtree of the root node is traversed. Here, inorder name itself suggests that the root node comes in between the left and the right subtrees.

We will discuss the inorder traversal using both recursive and iterative techniques. Let's first start with inorder traversal using recursion.

Inorder traversal using recursion

Example of inorder traversal

Now, let's see an example of inorder traversal. It will be easier to understand the procedure of inorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of the above tree using inorder traversal.

• Here, 40 is the root node. We move to the left subtree of 40, that is 30, and it also has subtree 25, so we again move to the left subtree of 25 that is 15. Here, 15 has no subtree, so print 15 and move towards its parent node, 25.
  
• Now, print 25 and move to the right subtree of 25.
  
• Now, print 28 and move to the root node of 25 that is 30.
  
• So, left subtree of 30 is visited. Now, print 30 and move to the right child of 30.
  
• Now, print 35 and move to the root node of 30.
  
• Now, print root node 40 and move to its right subtree.
  
• Now recursively traverse the right subtree of 40 that is 50.
  50 have subtree so first traverse the left subtree of 50 that is 45. 45 has no children, so print 45 and move to its root node.
  
• Now print 50 and move to the right subtree of 50 that is 60.
  
• Now recursively traverse the right subtree of 50 that is 60. 60 have subtree so first traverse the left subtree of 60 that is 55. 55 has no children, so print 55 and move to its root node.
  
• Now print 60 and move to the right subtree of 60 that is 70.
  
• Now print 70.
  

After the completion of inorder traversal, the final output is -

{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}

Complexity of Inorder traversal

The time complexity of Inorder traversal is O(n), where 'n' is the size of binary tree.

Whereas, the space complexity of inorder traversal is O(1), if we do not consider the stack size for function calls. Otherwise, the space complexity of inorder traversal is O(h), where 'h' is the height of tree.

Implementation of Inorder traversal

Now, let's see the implementation of inorder traversal in different programming languages.

Program: Write a program to implement inorder traversal in C language.

Output

Program: Write a program to implement inorder traversal in C++.

Output

Program: Write a program to implement inorder traversal in C#.

Output

Program: Write a program to implement inorder traversal in Java.

Output

So, that's all about the article. Hope the article will be helpful and informative to you.