102. Binary Tree Level Order Traversal 🚀

Solution Developed In:

The Question

For this article we will be covering Leetcode's '102. 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. If you're not familiar with this, you can read about it here. 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
2. Depth First Search
3. In-order traversal
4. Level Order Traversal
5. Queue

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

---

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;
};

Comments

[Samuel Hinchliffe 🚀]

Hey There 👋

---

Thank you for taking the time to look at my solution. I hope you found it interesting and useful.

If you're having difficulties understanding this solution or just need some clarity on a certain section of it. Please do not hesitate to contact me. We're all in this together and I'm happy to help. 😁

---

Contact me here: