Solving Leetcode 102. Binary Tree Level Order Traversal

From Leetcode:

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

What is being asked?

The questions seems to be pretty straight forward. Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7],

/*
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

*/

return its level order traversal as: [ [3], [9,20], [15,7] ]

What are ways to solve it?

There are multiple ways to solve this problem. One way would be to use a queue. We would start by putting the root node into the queue. Then, we would loop through the queue until it is empty. For each node in the queue, we would add its left and right child nodes (if they exist) to the queue. We would also add the value of the node to our result array.

What is the most optimal Way?

The most optimal way to solve this problem would be to use a breadth-first search algorithm.
The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. The space complexity is also O(n), since we need to store the nodes in the queue as well as the values in the result array. Let’s code this one.

var levelOrder = function(root) {
  // create a queue and result array
  let queue = [root];
  let result = [];
  
  // if the root is null, return an empty array
  if (!root) return result;
  
  // loop through the queue until it is empty
  while (queue.length > 0) {
    // store the size of the queue
    let size = queue.length;
    
    // create an array to store the values for this level
    let level = [];
    
    // loop through the queue
    for (let i = 0; i < size; i++) {
      // dequeue a node
      let node = queue.shift();
      
      // add the value of the node to the level array
      level.push(node.val);
      
      // if the node has a left child, add it to the queue
      if (node.left) queue.push(node.left);
      
      // if the node has a right child, add it to the queue
      if (node.right) queue.push(node.right);
    }
    
    // add the level array to the result array
    result.push(level);
  }
  
  // return the result array
  return result;
};