Inorder Tree Traversal (DFS) in java

Posted on Updated on

In our previous post we had discussed about different approaches of implementing Preorder tree traversal. In this article we shall discuss steps and different ways of implementing Inorder tree traversal.

There are different ways to traversal a tree in DFS such as:

  1. Preorder
  2. Inorder
  3. Postorder

Here in this article, we shall discuss steps and different approach of implementing Inorder tree traversal.

Steps for Inorder Tree Traversal are :

1) Traverse the left subtree, i.e., call Inorder(left-subtree)
2) Visit the root.
3) Traverse the right subtree, i.e., call Inorder(right-subtree)

tree

Inorder Traversal of above tree is 70, 40, 20, 50, 10, 30, 60

Time Complexity: O(n)

There are two ways to implement Inorder Tree Traversal.

1) Recursive
2) Iterative

Recursive solution for Inorder Tree Traversal :

Recursive solution for Inorder Traversal is similar to the steps we had discussed above. Algorithm for recursive solution is

Code for recursive solution

Output

Iterative solution for Inorder Traversal

To implement iterative solution for Inorder Traversal, we will be using Stack data structure. Algorithm for iterative solution is

Code for iterative solution

Output

Download code for Inorder Tree Traversal

InorderTraversal

Stay tuned for more updates and tutorials !!!

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.