Iterative Preorder And Postorder Of Generic Tree

I/P:

7

10 20 -1 30 40 -1 50

O/P:

10 20 30 40 50 

20 40 50 30 10

Analysis:

1. Initially add (root_node, -1) in the stack

2. Value at stack.peek()

    i.   if stack.peek() == -1, 

            then PRE-ORDER print, then increment the value from -1 to 0

    ii.  if stack.peek() >=0 && stack.peek() <= stack.peek(). children.size()-1

            then, goto child and push in stack

    iii. if stack.peek() == stack.peek().children.size() 

            then, POST-ORDER print, then pop()

package pep.Day31;

import java.io.*;
import java.util.*;

public class Iterative_Pre_and_PostOrder {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);
        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;
        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];
                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }
                st.push(t);
            }
        }
        return root;
    }

    private static class Pair {
        Node node;
        int state;

        Pair(Node node, int value) {
            this.node = node;
            this.state = value;
        }
    }

    public static void IterativePreandPostOrder(Node node) {

        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(node, -1));
        String preOrder = "", postOrder = "";
        while (!stack.isEmpty()) {
            Pair top = stack.peek();
            if (top.state == -1) {
                preOrder += top.node.data + " ";
                top.state++;
            } else if (top.state >= 0 && top.state < top.node.children.size()) {
                Pair test1 = new Pair(top.node.children.get(top.state++), -1);
                stack.push(test1);
            } else if (top.state == top.node.children.size()) {
                postOrder += top.node.data + " ";
                stack.pop();
            }
        }

        System.out.println(preOrder);
        System.out.println(postOrder);

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        IterativePreandPostOrder(root);
    }

}