Binary Tree Level Order Traversal | JS, Python, Java, C++ | Easy BFS Queue Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nA binary tree level order traversal generally recommends a **breadth first search** (**BFS**) approach with the use of a **queue** data structure. When we process a node (**curr**), we\'ll push the node\'s children onto the end of the **queue** in the order in which we want to traverse (in this case, left to right). In this way, we\'ll have finished putting the next row in the **queue** at the same time we finish iterating through this row.\n\nTo help us keep track of the rows, we just nest the main loop inside another loop. At the beginning of the outer loop, we capture the **queue** length, which will tell us how long the row is. Then we can iterate through that many nodes, popping them off the **queue**\'s front one at a time, then process any end-of-row instructions. In the case of this problem, that will mean pushing the current row array (**row**) onto our answer array (**ans**).\n\nWe\'ll continue this process until the **queue** is empty, at which point we will have reached the end of the binary tree, and can **return ans**.\n\n - _**Time Complexity: O(N)** where **N** is the number of nodes in the binary tree_\n - _**Space Complexity: O(N)** for our answer array_\n\n---\n\n#### ***Javascript Code:***\n```javascript\nvar levelOrder = function(root) {\n    let q = [root], ans = []\n    while (q[0]) {\n        let qlen = q.length, row = []\n        for (let i = 0; i < qlen; i++) {\n            let curr = q.shift()\n            row.push(curr.val)\n            if (curr.left) q.push(curr.left)\n            if (curr.right) q.push(curr.right)\n        }\n        ans.push(row)            \n    }\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n```python\nclass Solution:\n    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n        queue, ans = deque([root] if root else []), []\n        while len(queue):\n            qlen, row = len(queue), []\n            for _ in range(qlen):\n                curr = queue.popleft()\n                row.append(curr.val)\n                if curr.left: queue.append(curr.left)\n                if curr.right: queue.append(curr.right)\n            ans.append(row)\n        return ans\n```\n\n---\n\n#### ***Java Code:***\n```java\nclass Solution {\n    public List<List<Integer>> levelOrder(TreeNode root) {\n        List<List<Integer>> ans = new ArrayList<>();\n        if (root == null) return ans;\n        Deque<TreeNode> queue = new ArrayDeque<>();\n        queue.add(root);\n        while (!queue.isEmpty()) {\n            int qlen = queue.size();\n            List<Integer> row = new ArrayList<>();\n            for (int i = 0; i < qlen; i++) {\n                TreeNode curr = queue.poll();\n                row.add(curr.val);\n                if (curr.left != null) queue.add(curr.left);\n                if (curr.right != null) queue.add(curr.right);\n            }\n            ans.add(row);\n        }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n```c++\nclass Solution {\npublic:\n    vector<vector<int>> levelOrder(TreeNode* root) {\n        vector<vector<int>> ans;\n        if (!root) return ans;\n        deque<TreeNode*> queue;\n        queue.push_back(root);\n        while (!queue.empty()) {\n            int qlen = queue.size();\n            vector<int> row;\n            for (int i = 0; i < qlen; i++) {\n                TreeNode* curr = queue.front();\n                queue.pop_front();\n                row.push_back(curr->val);\n                if (curr->left) queue.push_back(curr->left);\n                if (curr->right) queue.push_back(curr->right);\n            }\n            ans.push_back(row);\n        }\n        return ans;\n    }\n};\n```
[]