Java solution using BFS with Comments: Time and Space: O(n)
This is a typical level order traversal with the only difference being that we need to keep track of the direction in which our node values in each level will b
This is a typical level order traversal with the only difference being that we need to keep track of the direction in which our node values in each level will be returned. If we want a left to right result, we insert values at the end of the list. Otherwise, we insert values at the beginning of the list to achieve a right to left result. For this, we will use a boolean variable to keep track of the direction to traverse.\n\nTime Complexity: O(n)\nSpace Complexity: O(n)\n\n```\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        // initialize an empty result list\n        List<List<Integer>> result = new ArrayList<List<Integer>>();\n        \n        // edge case\n        if (root == null) return result;\n        \n        // boolean variable to keep track of the direction to traverse nodes in a level\n        boolean leftToRight = true;\n        \n        // we\'ll be doing a BFS traversal\n        // so declare an empty queue\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n        \n        while (!queue.isEmpty()) {\n            int levelSize = queue.size();\n            \n            // we\'ll use LinkedList here instead of ArrayList\n            // since for right to left traversal\n            // we will insert node values at the beginning\n            // and with LinkedList we won\'t have to shift elements to the right when we do so\n            // which is the case in ArrayList\n            List<Integer> currentLevel = new LinkedList<>();\n            \n            for (int i = 0; i < levelSize; i++) {\n                TreeNode currentNode = queue.poll();\n                \n                if (leftToRight) {\n                    // add node value to end of list\n                    currentLevel.add(currentNode.val);\n                } else {\n                    // add node value to beginning of list\n                    currentLevel.add(0, currentNode.val);\n                }\n                \n                // add the children of the node to the queue\n                if (currentNode.left != null) {\n                    queue.offer(currentNode.left);\n                }\n                \n                if (currentNode.right != null) {\n                    queue.offer(currentNode.right);\n                }\n            }\n            \n            result.add(currentLevel);\n            \n            // reverse the direction for next level\n            leftToRight = !leftToRight;\n        }\n        \n        return result;\n    }
['Breadth-First Search', 'Queue', 'Java']