Solution: Binary Tree Level Order Traversal
Tags: algorithms, javascript, java, python
Published: 2021-05-20 07:58:22

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/1219328).*

---

#### [Leetcode Problem #102 (*Medium*): Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given the `root` of a binary tree, return _the level order traversal of its nodes' values_. (i.e., from left to right, level by level).

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|root = [3,9,20,null,null,15,7]
Output:|[[3],[9,20],[15,7]]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)
>
Example 2:||
|---:|---|
Input:|root = [1]
Output:|[[1]]
>
Example 3:||
|---:|---|
Input:|root = []
Output:|[]

---

#### ***Constraints:***
>
 - The number of nodes in the tree is in the range `[0, 2000]`.
 - `-1000 <= Node.val <= 1000`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

A 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.

To 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**).

We'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**.

 - _**Time Complexity: O(N)** where **N** is the number of nodes in the binary tree_
 - _**Space Complexity: O(N)** for our answer array_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var levelOrder = function(root) {
    let q = [root], ans = []
    while (q[0]) {
        let qlen = q.length, row = []
        for (let i = 0; i < qlen; i++) {
            let curr = q.shift()
            row.push(curr.val)
            if (curr.left) q.push(curr.left)
            if (curr.right) q.push(curr.right)
        }
        ans.push(row)            
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue, ans = deque([root] if root else []), []
        while len(queue):
            qlen, row = len(queue), []
            for _ in range(qlen):
                curr = queue.popleft()
                row.append(curr.val)
                if curr.left: queue.append(curr.left)
                if curr.right: queue.append(curr.right)
            ans.append(row)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int qlen = queue.size();
            List<Integer> row = new ArrayList<>();
            for (int i = 0; i < qlen; i++) {
                TreeNode curr = queue.poll();
                row.add(curr.val);
                if (curr.left != null) queue.add(curr.left);
                if (curr.right != null) queue.add(curr.right);
            }
            ans.add(row);
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        deque<TreeNode*> queue;
        queue.push_back(root);
        while (!queue.empty()) {
            int qlen = queue.size();
            vector<int> row;
            for (int i = 0; i < qlen; i++) {
                TreeNode* curr = queue.front();
                queue.pop_front();
                row.push_back(curr->val);
                if (curr->left) queue.push_back(curr->left);
                if (curr->right) queue.push_back(curr->right);
            }
            ans.push_back(row);
        }
        return ans;
    }
};
```