Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Binary Tree-Inorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for Inorder traversal.

Exam­ple:

Tree Traversals - Inorder

Tree Tra­ver­sals — Inorder

Ear­lier we have seen “What is Inorder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will solve it with iterative/Non Recur­sive manner.

Since we are not using recur­sion, we will use the Stack to store the tra­ver­sal, we need to remem­ber that inorder tra­ver­sal is, first tra­verse the left node then root fol­lowed by the right node.

Pseudo Code:

  1. Cre­ate a Stack.
  2. Push the root into the stack and set the root = root.left con­tinue till it hits the NULL.
  3. If root is null and Stack is empty Then
    1. return, we are done.
  4. Else
    1. Pop the top Node from the Stack and set it as, root = popped_Node.
    2. print the root and go right, root = root.right.
    3. Go to step 2.
  5. End If

See the ani­mated image below and code for more understanding.

 

Inorder Traversal - Non Recursive Approach

Inorder Tra­ver­sal — Non Recur­sive Approach

Com­plete Code:

Out­put:

4 2 5 1 3
4 2 5 1 3

You may also like...

  • swwl1992

    In the top­most pic­ture, the in-order tra­ver­sal should be “4 2 5 1 6 3 7″.
    In the Java code, the true con­di­tion can be replaced by “root != null || !nodes.isEmpty()”.