Preorder Tree Traversal without recursion in Java

Preorder Traversal Without recursion

In preorder traversal , root is visited first , then the left subtree and at last right subtree. Preorder traversal is also used to get an prefix expression of an expression. We need one explicit stack to implement this traversal without recursion.

Preorder Tree Traversal without recursion

Example - Preorder Tree Traversal Without Recursion

Example for preorder tree traversal without recursion

Steps to find preorder traversal using example :

  • Step 1: Create an empty stack and put the root element into it. i.e Stack-> 6.
  • Step 2: Now check if the stack is non- empty. if so , then  pop an element from the stack i.e. 6 and print it.
  • Step 3: Now check if  right child of popped element is not null. If so, then push the element into stack . So stack become , Stack->8.
  • Step 4: Similary check for  left child . If so , then push the left child into stack . So stack become , Stack->4,8 .And again goto step 3 and check if stack is not null.
  • Step 3: Again pop the top element from stack and print it. i.e print 4.
  • Step 4: Check if the right child is not null . If so , then push the right child into stack. i.e push(5)  . So stack become , Stack->5,8.
  • Step 5: Similarly , check for  left child. If it is not null , then push it into stack. i.e. push(2). So our stack become Stack->2,5,8. and again goto step 3 and check if stack is not null.
  • Step 3: Again pop an element from the stack and print it. i.e. print 2.Now stack become Stack->5,8.
  • Step 4: Now , it’s left and right child is not available hence we again goto step 3.
  • Step 3: pop an element from the stack i.e. pop(5) and print it.
  • Step 4: Now , As it’s left and right child is not available so move to step 3.
  • Step 3: pop an element from the stack i.e. 8 and print it.
  • Step 4: Now, check for it’s right child as 9 is it’s right child so put it into the stack. and goto step 3 as there is no left child of element 8.
  • Step 3: pop the element from the stack i.e. 9 and print it . Now our stack becomes empty, so stop.
Therefore the sequence will be printed as 6,4,2,5,8,9

Algorithm

  1.  If root is null , simply return.
  2. else , create an empty stack  and push root node into it.
  3. Check if the Stack is non-empty . If so, pop the element from the stack and print it.
  4. Now, Check if the right child of popped element is available or not . if available then push it into stack.
  5. Similarly , Check for the left child . If available then push it into the stack.
  6. Now , continue step 3 ,4,5  until stack becomes empty .
  7. If Stack becomes empty then stop.

CODE FOR PREORDER TRAVERSAL WITHOUT RECURSION.

//Preorder Traversal Without recursion

/*Node class containing left and right child of current node and key value.*/

import java.util.*;

class Node{
   int value;
   Node left,right;

   public Node(int value)
   {
       this.value=value;
       left=null;
       right=null;
   }
}
class Preorder{
   Node root; //root of the tree
   public Preorder(){
   root=null;
}
   /*function for Preorder traversal of the binary tree*/
   public void preorder()
   {
       if(root ==null)
       return ;
       Stack stack=new Stack(); //creating an empty stack.
       stack.push(root); //inserting an element into stack.
       while(!stack.isEmpty())
       {
           Node temp=stack.pop(); //removing the top element from stack.
           System.out.print(temp.value+" ");
           if(temp.right!=null)
           stack.push(temp.right); //inserting into stack
           if(temp.left!=null)
           stack.push(temp.left); //inserting into stack
       }
   }
   public static void main(String[] args)
   {
       Preorder t=new Preorder();
       t.root=new Node(6);
       t.root.left=new Node(4);
       t.root.right=new Node(8);
       t.root.left.left=new Node(2);
       t.root.left.right=new Node(5);
       t.root.right.right=new Node(9);
       t.preorder();
   }
}

Output:

6 4 2 5 8 9

TIME AND SPACE COMPLEXITY OF PREORDER TRAVERSAL

Time Complexity :

O(n)

Space complexity:

O(n)