[Amazon] Binary Tree Zigzag Level Order Traversal

Problem: Given a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Input: root = [1]
Output: [[1]]

Input: root = []
Output: []

Approach: We can use two stacks to solve this problem easily but this will take extra space. Let's try to optimize the space.

What we can do is, while doing level order traversal, at every level we can allocate an array of the size equals to the number of nodes in the current level. We can have an boolean variable say leftToRight which will be true initially and then after every level it will be not of itself. 

Now in this allocated array, we will store node values according to leftToRight i.e. if it is true then we store value from start to end, if it is false then we store value from end to start.

In the implementation you will see that I am creating a list from the array but we can ignore it if the return type is IList<int[]>.

That's all!

Implementation in C#:

Using Two stacks:

    public IList<IList<int>> ZigzagLevelOrder(TreeNode root)

    {

        IList<IList<int>> result = new List<IList<int>>();

        if (root == null)

        {

            return result;

        }

        var stacks = new Stack<TreeNode>[] {

                                            new Stack<TreeNode>(),

                                            new Stack<TreeNode>()

                                           };

        int turn = 0;

        stacks[0].Push(root);

        bool leftToRight = true;

        var tempNodes = new TreeNode[2];

        while (stacks[turn].Count != 0)

        {

            List<int> currRow = new List<int>();

            int rowSize = stacks[turn].Count;

            int nextStackIndex = turn ^ 1;

            while (rowSize > 0)

            {

                var node = stacks[turn].Pop();

                currRow.Add(node.val);

                tempNodes[0] = leftToRight ? node.left : node.right;

                tempNodes[1] = leftToRight ? node.right : node.left;

                if (tempNodes[0] != null)

                {

                    stacks[nextStackIndex].Push(tempNodes[0]);

                }

                if (tempNodes[1] != null)

                {

                    stacks[nextStackIndex].Push(tempNodes[1]);

                }

                --rowSize;

            }

            leftToRight = !leftToRight;

            turn = nextStackIndex;

            result.Add(currRow);

        }

        return result;

    }

Without using stacks:

    public IList<IList<int>> ZigzagLevelOrder(TreeNode root)

    {

        var result = new List<IList<int>>();

        if (root == null)

        {

            return result;

        }

        Queue<TreeNode> queue = new Queue<TreeNode>();

        queue.Enqueue(root);

        bool leftToRight = true;

        while (queue.Count != 0)

        {

            int size = queue.Count;

            int[] lvlElements = new int[size];

            for (int i = 0; i < size; ++i)

            {

                var node = queue.Dequeue();

                int index = leftToRight ? i : size - i - 1;

                lvlElements[index] = node.val;

                if (node.left != null)

                {

                    queue.Enqueue(node.left);

                }

                if (node.right != null)

                {

                    queue.Enqueue(node.right);

                }

            }

            result.Add(new List<int>(lvlElements));

            leftToRight = !leftToRight;

        }

        return result;

    }

Complexity: O(n)