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 — Preorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pre­order tra­ver­sal.

Tree Traversals - Preorder

Tree Tra­ver­sals — Preorder

Exam­ple:

Ear­lier we have seen “What is pre­order 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 pre­order tra­ver­sal is, first tra­verse the root node then left node fol­lowed by the right node.

Pseudo Code:

  1. Cre­ate a Stack.
  2. Print the root and push it to Stack and go left i.e root=root.left and 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. Go right, root = root.right.
    3. Go to step 2.
  5. End If

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

Preorder traversal

Pre­order traversal

 

Com­plete Code:

Out­put:

1 2 4 5 3 6 7
1 2 4 5 3 6 7

You may also like...

  • Bandla palli Bhukailas Reddy

    if (root == null) {
    root = stack.pop();
    root = root.right;
    }

    we need to pop from stack when root is null in iter­a­tive tra­ver­sal. Please cor­rect that.

  • lipsa patel

    Another solu­tion same as Non Recur­sive Post Order Traversal

    //Non-recursive pre order tra­ver­sal
    pri­vate void nonRecursivePreOrderTraversal(Node root) {
    if (root != null) {

    System.out.println(“Non Recur­sive Pre Order Tra­ver­sal:”);
    Stack stack1 = new Stack();

    //Push root node
    stack1.push(root);

    while(!stack1.isEmpty()) {
    //Pop from stack1
    Node­poppedNode = stack1.pop();

    System.out.print(poppedNode.data + “->”);

    //Push right
    if (poppedNode.right != null) {
    stack1.push(poppedNode.right);
    }

    //Push left
    if (poppedNode.left != null) {
    stack1.push(poppedNode.left);
    }
    }
    }
    }