Binary Tree traversal using Iteration- Algo 11

Binary tree traversal can be implemented either using Recursion which  is simple and maximum work is done by stack call and second , by using Iteration which require additional data structure like Stack to record previous call which helps in tracking traversal.

Java Implementation of Iterative Binary Tree Traversal

import java.util.Stack;

public class BinarySearchIterativeTraversal {

    Node root;

    public static void main(String[] args) {

       BinarySearchIterativeTraversal tree = new                 BinarySearchIterativeTraversal();

        tree.root = new Node(100);

        tree.root.leftChild = new Node(50);

        tree.root.rightChild = new Node(150);

        tree.root.leftChild.leftChild = new Node(25);

        tree.root.leftChild.rightChild = new Node(35);

        tree.root.rightChild.leftChild = new Node(125);

        tree.root.rightChild.rightChild = new Node(200);

        System.out.println("Print InOrder (Left-Root-Right)");

        tree.IterativeInorder();

        System.out.println("\n\n"+"Print PostOrder(Left-Right-Root)");

        tree.IterativePostOrder();

    }

    void IterativePostOrder(){IterativePostOrder(root);}

    void IterativeInorder(){IterativeInorder(root);}

   

    // Left - Root- Right

    void IterativeInorder(Node root){

         if(root==null)

             return;

         Stack<Node> stack= new Stack<Node>();

         while(true){

             if(root!=null){

                 stack.push(root);

                 root=root.leftChild;

             }

             else{

                 if(stack.isEmpty())

                      break;

                 root=stack.pop();

                 System.out.println(root.data);

                 root=root.rightChild;

             }

         }

    }

    // Left- Right - Root

    void IterativePostOrder(Node root){

         if(root==null)

             return;

         Stack<Node> s1= new Stack<Node>();

         Stack<Node> s2= new Stack<Node>();

         s1.push(root);

         while(!s1.isEmpty()){

             root=s1.pop();

             s2.push(root);

             if(root.leftChild!=null)

                 s1.push(root.leftChild);

             if(root.rightChild!=null)

                 s1.push(root.rightChild);

         }

         while(!s2.isEmpty())

         {

             root=s2.pop();

             System.out.println(root.data);

         }

        

    }

}

Output:

Print InOrder (Left-Root-Right)

25

50

35

100

125

150

200

Print PostOrder(Left-Right-Root)

25

35

50

125

200

150

100