Binary Tree – Preorder Traversal – Non Recursive Approach

by · December 5, 2015

Objective: Given a binary tree, write a non recursive or iterative algorithm for preorder traversal.

Tree Traversals - Preorder

Tree Traversals – Preorder

Example:

Earlier we have seen “What is preorder traversal and recursive algorithm for it“, In this article we will solve it with iterative/Non Recursive manner.

Since we are not using recursion, we will use the Stack to store the traversal, we need to remember that preorder traversal is, first traverse the root node then left node followed by the right node.

Pseudo Code:

  1. Create 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 animated image below and code for more understanding.

Preorder traversal

Preorder traversal

 

Complete Code:



Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Tags:

  • Bandla palli Bhukailas Reddy

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

    we need to pop from stack when root is null in iterative traversal. Please correct that.

  • lipsa patel

    Another solution same as Non Recursive Post Order Traversal

    //Non-recursive pre order traversal
    private void nonRecursivePreOrderTraversal(Node root) {
    if (root != null) {

    System.out.println(“Non Recursive Pre Order Traversal:”);
    Stack stack1 = new Stack();

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

    while(!stack1.isEmpty()) {
    //Pop from stack1
    NodepoppedNode = 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);
    }
    }
    }
    }

Follow:

Select level

Beginner
Intermediate
Expert

Follow me on Twitter

%d bloggers like this: