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

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

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

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.