Level order Linewise Zig Zag

I/P:

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:

10 40 30 20 50 60 70 80 90 100 120 110

package pep.Day28;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class LevelOrder_Linewise_Zigzag {
    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;
    }

    public static int size(Node node) {
        int s = 0;

        for (Node child : node.children) {
            s += size(child);
        }
        s += 1;

        return s;
    }

    public static void levelOrderLinewiseZZ(Node node) {
        // write your code here

        Stack<Node> mainStack = new Stack<>();
        Stack<Node> childStack = new Stack<>();

        mainStack.add(node);
        int level = 1;
        while (!mainStack.isEmpty()) {
            // remove
            Node out = mainStack.pop();
            // print
            System.out.print(out.data + " ");

            // add children
            if (level % 2 == 0) {
                // for right to left printing of node
                for (int i = out.children.size() - 1; i >= 0; i--)
                    childStack.push(out.children.get(i));
            } else {
                // for left to right printing of node
                for (int i = 0; i < out.children.size(); i++)
                    childStack.push(out.children.get(i));
            }

            // swaping of mainStack and childStack.
            // also, incrementing the level
            if (mainStack.isEmpty()) {
                mainStack = childStack;
                childStack = new Stack<>();
                System.out.println();
                level++;
            }
        }
    }

    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);
        levelOrderLinewiseZZ(root);
    }

}

Time Complexity:

O(n) If you notice carefully we are just inserting one node in a stack and then popping it. So for every node, we are performing constant time operations and hence we will have n*O(1) = O(n) time complexity.

Space Complexity:

O(n) at worst case In the worst case, the child stack might have n-1 nodes. Look at the following tree for example.

So the worst-case space complexity will be O(n).