Day 50 || BFS || Easiest Beginner Friendly Sol
Intuition of this Problem:\nThe problem asks us to perform a level-order traversal of a binary tree, but with a slight modification - we need to return the node
# Intuition of this Problem:\nThe problem asks us to perform a level-order traversal of a binary tree, but with a slight modification - we need to return the nodes of each level in a zigzag order, starting from left to right and then right to left for the next level, and so on.\n\nThe intuition behind this problem is to use a queue-based BFS (Breadth First Search) approach to traverse the tree level by level, and maintain the order of the nodes in each level by keeping track of the level number. For every even numbered level, we add the nodes to the result list from left to right, and for every odd numbered level, we add the nodes to the result list from right to left.\n\nBy using this approach, we can ensure that we visit all the nodes in the tree in a level-order manner, while maintaining the zigzag order of the nodes at each level.\n<!-- Describe your first thoughts on how to solve this problem. -->\n**NOTE - PLEASE READ APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Approach for this Problem:\n1. If the root node is null, return an empty vector.\n2. Initialize a queue of type TreeNode* and push the root node into it.\n3. Initialize a variable to keep track of the current level (even or odd). We start with even level.\n4. While the queue is not empty:\n    - a. Get the size of the queue and create a new vector to hold the elements of the current level.\n    - b. Loop through the nodes at the current level and add their values to the vector.\n    - c. If the current level is even, add the node\'s value to the end of the vector; otherwise, add it to the beginning.\n    - d. If the node has a left child, add it to the queue.\n    - e. If the node has a right child, add it to the queue.\n    - f. Increment the level counter.\n    - g. Add the vector containing the elements of the current level to the answer vector.\n1. Return the answer vector.\n<!-- Describe your approach to solving the problem. -->\n\n# Humble Request:\n- If my solution is helpful to you then please **UPVOTE** my solution, your **UPVOTE** motivates me to post such kind of solution.\n- Please let me know in comments if there is need to do any improvement in my approach, code....anything.\n- **Let\'s connect on** https://www.linkedin.com/in/abhinash-singh-1b851b188\n\n![57jfh9.jpg](https://assets.leetcode.com/users/images/c2826b72-fb1c-464c-9f95-d9e578abcaf3_1674104075.4732099.jpeg)\n\n# Code:\n```C++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        if (root == nullptr)\n            return {};\n        vector<vector<int>> ans;\n        queue<TreeNode*> q;\n        //strating from even level\n        int isLevelEvenOrOdd = 0;\n        q.push(root);\n        while (!q.empty()) {\n            int nodesInLevel = q.size();\n            vector<int> tempVec;\n            while (nodesInLevel--) {\n                TreeNode* temp = q.front();\n                q.pop();\n                if (isLevelEvenOrOdd % 2 == 0) \n                    tempVec.push_back(temp -> val);\n                else \n                    tempVec.insert(tempVec.begin(), temp -> val);\n                    \n                if (temp -> left != nullptr)\n                    q.push(temp -> left);\n                if (temp -> right != nullptr)\n                    q.push(temp -> right);\n            }   \n            isLevelEvenOrOdd++;\n            ans.push_back(tempVec);\n        }\n        return ans;\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        queue<TreeNode*> q;\n        q.push(root);\n        bool left_to_right = true;\n        while (!q.empty()) {\n            int size = q.size();\n            vector<int> level(size);\n            for (int i = 0; i < size; i++) {\n                TreeNode* node = q.front();\n                q.pop();\n                if (left_to_right)\n                    level[i] = node->val;\n                else\n                    level[size - i - 1] = node->val;\n                if (node->left) {\n                    q.push(node->left);\n                }\n                if (node->right) {\n                    q.push(node->right);\n                }\n            }\n            result.push_back(level);\n            left_to_right = !left_to_right;\n        }\n        return result;\n    }\n};\n```\n```Java []\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> ans = new ArrayList<>();\n        if (root == null)\n            return ans;\n        Queue<TreeNode> q = new LinkedList<>();\n        q.offer(root);\n        int level = 0;\n        while (!q.isEmpty()) {\n            int size = q.size();\n            List<Integer> levelNodes = new ArrayList<>();\n            while (size-- > 0) {\n                TreeNode curr = q.poll();\n                if (level % 2 == 0) {\n                    levelNodes.add(curr.val);\n                } else {\n                    levelNodes.add(0, curr.val);\n                }\n                if (curr.left != null) {\n                    q.offer(curr.left);\n                }\n                if (curr.right != null) {\n                    q.offer(curr.right);\n                }\n            }\n            level++;\n            ans.add(levelNodes);\n        }\n        return ans;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n        if not root:\n            return []\n        q = collections.deque([root])\n        level = 0\n        ans = []\n        while q:\n            level_nodes = []\n            for _ in range(len(q)):\n                curr = q.popleft()\n                if level % 2 == 0:\n                    level_nodes.append(curr.val)\n                else:\n                    level_nodes.insert(0, curr.val)\n                if curr.left:\n                    q.append(curr.left)\n                if curr.right:\n                    q.append(curr.right)\n            ans.append(level_nodes)\n            level += 1\n        return ans\n\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity: **O(n)**, where n is the number of nodes in the binary tree, since we need to traverse all the nodes.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(w)**, where w is the maximum width of the binary tree (i.e., the maximum number of nodes at any level). In the worst case, the queue will contain all the nodes at the last level, so the space complexity is proportional to the width of the tree.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Breadth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']