Easy and Optimized code Best Explanation🔥🔥| TC-O(N).
PLZ UPVOTE\n\n# Intuition\nThe code uses a breadth-first search (BFS) approach to traverse the binary tree level by level. It maintains a boolean variable flag 
# **PLZ UPVOTE**\n\n# Intuition\nThe code uses a breadth-first search (BFS) approach to traverse the binary tree level by level. It maintains a boolean variable flag to determine whether to add elements from left to right or right to left in each level. If flag is true, elements are added from left to right, and if flag is false, elements are added from right to left.\n\n# Approach\n1. The code uses a queue to perform level order traversal. The queue is initially populated with the root of the tree.\n2. Inside the loop, it processes each level:\n- It calculates the size of the current level and creates a list arr2 to store the values of the nodes at that level.\n- For each node in the level, it adds its left and right children to the queue if they exist.\n- Depending on the value of the flag, it either adds the value of the node to the end of the arr2 list or adds it to the beginning (in reverse order).\n- After processing all nodes at the current level, it toggles the value of the flag for the next level.\n- The arr2 list is then added to the result list arr.\n3. The process continues until all levels of the tree are processed.\n\n# Complexity\n- Time complexity:\nThe time complexity of the code is O(N), where N is the number of nodes in the binary tree. In the worst case, every node is visited once. The inner loop, which processes each level, runs in O(N) time overall. The queue operations and list manipulations are constant time for each node.\n\n- Space complexity: O(N) because only queue of size n is taken as extra space.\n\n# Code\n```Java []\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> arr= new ArrayList<>();\n        if(root==null){\n            return arr;\n        }\n        Queue<TreeNode> q= new LinkedList<>();\n        q.add(root);\n        boolean flag=true;\n        while(!q.isEmpty()){\n            int n= q.size();\n            List<Integer> arr2= new ArrayList<>(n);\n            for(int i=0; i<n; i++){\n                if(q.peek().left!=null){\n                    q.add(q.peek().left);\n                }\n                if(q.peek().right!=null){\n                    q.add(q.peek().right);\n                }\n                if(flag){\n                    arr2.add(q.poll().val);\n                }else{\n                    arr2.add(0,q.poll().val);\n                }\n            }\n            flag=!flag;\n            arr.add(arr2);\n        }\n        return arr;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>> result;\n        if (root == nullptr) {\n            return result;\n        }\n\n        queue<TreeNode*> q;\n        q.push(root);\n        bool flag = true;\n\n        while (!q.empty()) {\n            int n = q.size();\n            vector<int> levelValues(n);\n\n            for (int i = 0; i < n; ++i) {\n                if (q.front()->left != nullptr) {\n                    q.push(q.front()->left);\n                }\n                if (q.front()->right != nullptr) {\n                    q.push(q.front()->right);\n                }\n\n                if (flag) {\n                    levelValues[i] = q.front()->val;\n                } else {\n                    levelValues[n - 1 - i] = q.front()->val;\n                }\n\n                q.pop();\n            }\n\n            flag = !flag;\n            result.push_back(levelValues);\n        }\n\n        return result;\n    }\n};\n```\n```Python []\nclass Solution:\n    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n        result = []\n        if not root:\n            return result\n\n        queue = deque([root])\n        flag = True\n\n        while queue:\n            n = len(queue)\n            level_values = [0] * n\n\n            for i in range(n):\n                node = queue.popleft()\n                if node.left:\n                    queue.append(node.left)\n                if node.right:\n                    queue.append(node.right)\n\n                if flag:\n                    level_values[i] = node.val\n                else:\n                    level_values[n - 1 - i] = node.val\n\n            flag = not flag\n            result.append(level_values)\n\n        return result\n```\n![upvote.jpg](https://assets.leetcode.com/users/images/c3ace874-43d2-43f4-a629-efaef82c532b_1703742442.869688.jpeg)\n\n
['Breadth-First Search', 'Queue', 'Python', 'C++', 'Java']