102. Binary Tree Level Order Traversal 🚀
Tags: javascript, tutorial, leetcode, programming
Published: 2022-05-03 18:29:13

## Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)' question. This question is rated as a **Medium** question.

Question:

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

Example:
```
    3
   / \
  9  20
    /  \
   15   7
```
```
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
```

## Explaining The Question
This Question is rated **Medium**. Which I believe is accurate for this Binary Tree question. 

So we're given a ***Binary Tree*** that needs to be traversed. We need to return the level order traversal of its nodes' values. What this mean's is that each layer in a Binary Tree must have it's own array to indicate what's in that array. 

Meaning, that if you have **10 layers** to a *Binary Tree*, you must have 10 arrays. Which represents the **10 layers** of the ***Binary Tree***.

Now, you're likely to be familiar with [Level Order Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Level-order_traversal). If you're not familiar with this, you can read about it [here](https://en.wikipedia.org/wiki/Tree_traversal#Level-order_traversal). I suggest you practice this technique of traversal until you're the master. Because without that knowledge you ***cannot*** solve this question.

##  Recommended Knowledge
1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [In-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order)
4. [Level Order Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Level-order_traversal)
5. [Queue](https://en.wikipedia.org/wiki/Queue_(data_structure))

## What do we know?
1. We have been given a ***Binary Tree***.
2. Our tree has ***multiple layers***
3. These layers need to be traversed and stored.
4. Each layer must have it's own ***row***
5. We will return the collection of these arrays. Which will be a array of rows.

## How we're going to do it:

We're going to conduct a variation of the iterative layer order traversal (In-order) algorithm. Which mean's we will visit each node, in a layer by layer format. For this [question](https://leetcode.com/problems/binary-tree-level-order-traversal/) you should already know how to do this.

What we're going to different to the normal level order traversal is that we're going to use a ***for*** loop to iterate through each layer. Each layer is represented by what's in the ***queue***. Although the key difference here is that we will ***ONLY*** visit the nodes that are on that layer, but despite this, we're going to know what nodes come next. It's a little confusing.

So for each layer, we're going to add the given nodes value to the `row array` and then we're going to add the children of the node to the queue. '***But surely we would just end up going through the entire tree that way and not layer by layer!!***'. Yep, that would be the case if we didn't keep track of the queues length before we start adding more to it, but we do keep track of it. So we always know the length of the layer.

1. Firstly, we're going to declare our `queue` for our Level Order Traversal of the tree. We're also going to declare our `level_order_array` which will be our return value. Here will push each `row` to it.
2. We're going to declare our `row` array. Which will of course be a representative of each binary trees layer.
3. So we're going to store the length of the queue. Which will be the length of the current layers length. For each node in that layer, we're going to add it to the `row` array. While also adding their children to the ***queue***. But because we only want the nodes of that layer, we're going to only for loop over the initial length of the given `queue`.

## Big O Notation:
* Time Complexity:   *O(**n**)* | Where ***n*** is the number of nodes in our ***Binary Tree*** | As we're going to traverse all of the nodes within the tree.
* Space Complexity: *O(**q**)* | Where ***q*** is the length of the ***Binary Tree's Queue*** 

## Leetcode Results:

See Submission Link: 

* Runtime: 77 ms, faster than ***64.38%*** of JavaScript online submissions for Binary Tree Level Order Traversal
* Memory Usage: 44.5 MB, less than ***35.08%*** of JavaScript online submissions for Binary Tree Level Order Traversal

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/692372150/)


***

## The Solution
```

var levelOrder = function (root) {

    // Empty tree
    // Return a empty array
	if (!root) {
		return [];
	}

    // Level Order Array, will store each row of the tree
	let level_order_array = [];
	let queue = [root];

    // We're going to be using a iterative approach to this.
    // With use of a queue we're able to achieve level order traversal.
	while (queue.length) {

        // We're going to create a new row each time
        // we encounter a new level.
		let row = [];

        // This is the important part.
        // We keep track of the initial length of the queue
        // We do this because, as we iterate through the queue we don't
        // want to accidentally pick up items from another.
		let queue_len = queue.length;

        // So for every item currently in the queue
        // we're going to add it to the row
        // All the while adding new items to the queue,
        // but because we kept memory of the input length
        // we will only ever pick up the items for that row.
		for (let i = 0; i < queue_len; i++) {

            // Get the node, by popping it off the queue
			let node = queue.pop();

            // Add the node to the row (This row is the given layer)
			row.push(node.val);

            // Just like in a normal level order traversal,
            // when we see a child node, we add it to the queue,
            // but because we kept memory of the input length
            // we won't technically run these children items
            // until we reach their row.
			node.left ? queue.unshift(node.left) : null;
			node.right ? queue.unshift(node.right) : null;
		}

        // So we have gone through the entire queue.
        // Push that row to the level order array.
		level_order_array.push(row);
	}

	return level_order_array;
};

```