DEV Community

Cover image for Inorder Traversal - Iterative
Rohith V
Rohith V

Posted on

Inorder Traversal - Iterative

Problem Statement

Given a binary tree. Find the inorder traversal of the tree without using recursion.

Sample Test Cases

Example 1

Input:

           1
         /    \
       2       3
      /   \
    4     5
Enter fullscreen mode Exit fullscreen mode

Output: 4 2 5 1 3
Explanation:
Inorder traversal (Left->Root->Right) of
the tree is 4 2 5 1 3.

Example 2

Input:

            8
          /   \
        1      5
        \     /  \
         7   10   6
             \  /
             10 6
Enter fullscreen mode Exit fullscreen mode

Output: 1 7 10 8 6 10 5 6
Explanation:
Inorder traversal (Left->Root->Right)
of the tree is 1 7 10 8 6 10 5 6.

Task and Constraints

You don't need to read input or print anything. Your task is to complete the function inOrder() which takes the root of the tree as input and returns a list containing the inorder traversal of the tree, calculated without using recursion.

Expected time complexity: O(N)
Expected auxiliary space: O(N)

Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5

What is inorder traversal

It is a type of traversal in tree where first we go to left of current node, then the node, then to the right of the node
That is left -> root -> right.

It can be easily done using recursion:

ArrayList<Integer> inOrder(Node root)
    {
        // Code
        if (root == null)
            return new ArrayList<>();
        ArrayList<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    void inorder(Node node, ArrayList<Integer> result) {
        if (node == null)
            return;
        inorder(node.left, result);
        result.add(node.data);
        inorder(node.right, result);
    }
Enter fullscreen mode Exit fullscreen mode

It can also be done using iterative method where we use a stack and do the processing

Iterative Approach

So here we make use of stack as usual and move to the left of the root until we reach the leaf.
Then that left node is added to the result and processed back and check with the right node.

  • Let us have a current node = root. current = root.

  • We also make use of a stack . Stack<Node> stack = new Stack<>().

  • Until the stack is null or current is null, we start the outer loop

  • Now inside this loop, we move to the left of current node until it is null and each time we add the nodes into the stack.

while (current != null) {
     stack.push(current)l
     current = current.left;
}
Enter fullscreen mode Exit fullscreen mode
  • Now if the current reaches null, it means we reach the leaf node, so we pop it out, add it into the result and then check with current.right
current = stack.pop();
result.add(current.data);
current = current.right;
Enter fullscreen mode Exit fullscreen mode
  • Finally return the result.

Code walkthrough

       1
     /    \
   2       3
  /   \
4     5
Enter fullscreen mode Exit fullscreen mode
  • stack = [] result = [] current = 1

  • push 1 -> stack[1] result = [] current.left = 2

  • push 2 -> stack[2, 1] result = [] current.left = 4

  • push 4 -> stack[4, 2, 1] result = [] current.left = null

  • pop 4 -> stack[2, 1] result = [4] current = 4

  • right of 4 is also null current.right = null

  • pop 2 -> stack[1] result = [4, 2] current.right = 5

  • push 5 -> stack[5, 1] result = [4, 2] current.left = null

  • pop 5 -> stack[1] result = [4, 2, 5] we processed with left child of 1 current = 1

  • pop 1 -> stack[] result = [4, 2, 5, 1] current goes to right of 1, ie 3 current.right = 3

  • push 3 -> stack[3] result = [4, 2, 5, 1] current.left = null

  • pop 3 -> stack[] result = [4, 2, 5, 1, 3] current.right = null

Now both stack is empty and current is null, so we return result

Complexity

time complexity: O(N)
auxiliary space: O(N)

Code

class Solution
{
    // Return a list containing the inorder traversal of the given tree
    ArrayList<Integer> inOrder(Node root)
    {
        // Code
        if (root == null)
            return new ArrayList<>();
        ArrayList<Integer> result = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        Node current = root;
        while (!stack.isEmpty() || current != null) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.data);
            current = current.right;
        }
        return result;
    }

}
Enter fullscreen mode Exit fullscreen mode

GitHub logo Rohithv07 / LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions

Billboard image

Synthetic monitoring. Built for developers.

Join Vercel, Render, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay