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., fromleft
toright
, 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
What do we know?
- We have been given a Binary Tree.
- Our tree has multiple layers
- These layers need to be traversed and stored.
- Each layer must have it's own row
- 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.
- Firstly, we're going to declare our
queue
for our Level Order Traversal of the tree. We're also going to declare ourlevel_order_array
which will be our return value. Here will push eachrow
to it. - We're going to declare our
row
array. Which will of course be a representative of each binary trees layer. - 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 givenqueue
.
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;
};
Top comments (1)
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: