Sunday, December 3, 2023
HomeDSASolving Leetcode 102. Binary Tree Level Order Traversal

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

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:
[
,
[9,20],
[15,7]
]

*/```

return its level order traversal as: [ , [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 ARTICLES