Preorder, Inorder and Postorder traversals without Recursion in Java

In this Java tutorial, we will learn how to traverse a tree without recursion in Java. We will implement preorder, inorder and postorder traversals without recursion in Java.

Preorder Traversal in Java

In a preorder traversal, we first visit the node itself then we visit the left and right subtrees of the node. For iterative preorder traversal, we must have a stack. Steps for preorder traversal:

1. Initialize an empty stack and push the root of the tree in it.
2. While the stack is not empty, do:
   i. Pop an item from the stack and add it to the ArrayList.
   ii. Push the right child of the popped node into the stack.
   iii. Push the left child of the popped node into the stack.

Inorder Traversal in Java

In an inorder traversal, we first visit the left subtree, then the node and finally the right subtree of the node. Steps for iterative inorder traversal:

1. Create an empty stack.
2. Set current as the root node.
3. While both current != null and stack is not empty are not false, do:
   i. While current is not null, push the current node into the stack. And, current becomes current.left.
   ii. Pop the node from the stack and add it to the ArrayList.
   iii. Set current as the right of the popped node.

Postorder Traversal in Java

In a postorder traversal, we first visit the left and right subtree of the node and then visit the node. Steps for iterative postorder traversal:

1. Create an empty stack.
2. Push the root node of the tree to the stack.
3. While stack is not empty, do:
   i. Pop the node from the stack.
   ii. Add the popped node to the first index in ArrayList.
   iii. If node.left is not null, then push it to the stack.
   iv. If node.right is not null, then push it to the stack.

Program to find Preorder, Inorder, and Postorder traversals without recursion in Java

 

import java.util.ArrayList;
import java.util.Stack;

public class treeTraversals {
    public static void main(String[] args) {
        /* Tree:
                      50
                     /  \
                    10   20
                  /  \   /  \
                30   60  70  80
                 \       /
                 40     90
         */
        TreeNode root = new TreeNode(50);
        root.left = new TreeNode(10);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(30);
        root.left.left.right = new TreeNode(40);
        root.left.right = new TreeNode(60);
        root.right.left = new TreeNode(70);
        root.right.right = new TreeNode(80);
        root.right.left.left = new TreeNode(90);

        System.out.println("Preorder traversal: " + preorderTraversal(root));
        System.out.println("Inorder traversal : "+ inorderTraversal(root));
        System.out.println("Postorder traversal: " + postorderTraversal(root));


    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }

    public static ArrayList<Integer> preorderTraversal(TreeNode A) {

        ArrayList<Integer> al = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(A);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            al.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return al;
    }

    public static ArrayList<Integer> inorderTraversal(TreeNode A) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> al = new ArrayList<>();
        TreeNode curr = A;

        while (!stack.isEmpty() || curr != null) {

            while (curr != null) {

                stack.push(curr);
                curr = curr.left;
            }
            TreeNode node = stack.pop();
            al.add(node.val);

            curr = node.right;
        }
        return al;
    }

    public static ArrayList<Integer> postorderTraversal(TreeNode A) {

        Stack<TreeNode> stack = new Stack<>();
        stack.push(A);
        ArrayList<Integer> al = new ArrayList<>();

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            al.add(0, node.val);

            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        return al;
    }

}

 

You can also read:

• Working with HashMap (Insertion, Deletion, Iteration) in Java
• Working With LinkedList (Adding, Removing and Retrieving Elements) in Java