Coding Interview Club

Prepare for coding interviews in simple and structured steps

Inorder Traversal Without Using Recursion

Category: 
Problem: 

Inorder Traversal Without Using Recursion

Approach: 

We can use a stack data structure to do this:

  • Initialize current node as root
  • Create a stack.
  • Do following until current is NULL and stack is empty:
    • Push the current node to stack and set current = current.left until current is NULL
    • If current is NULL and stack is not empty then 
      • Pop the top item from stack into current.
      • Print current,
      • Set current = current.right 
Solution: 

void inorder(TreeNode n)

{

  TreeNode current = n;

  Stack s = new Stack();

  while((current ! = null) || !s.isEmpty())

  {

    if(current!=null)

    {

      s.push(current);

      current = current.left;

    }

    else{

      current = s.pop();

      print(current);

      current = current.right;

    }

  }

}

 

Complexity

Time complexity is O(n)

Extra space for stack also will be taken.

Back to Top