Recursion

Given the root node of a binary tree `root`

, return an array containing the Breadth-First traversal of the tree.

**Example:**

$\notag
\def\t#1{\texttt{#1}}
\large\t{=> returns } \Big[ \t{[1], [2,3], [4,5,6]} \Big]$

First Few Test Cases:

Since this is a BFS problem, we can jump right into the code. Here's the code for a BFS that goes layer by layer, which you should memorize:

Now let's modify this code to get the solution.
We want to add all the values in a layer to an array, which we'll call `layer`

. We're done with a layer, we'll add it to our solution `soln`

.
You can stick some lines of code into the above BFS to code this up:

Time Complexity $O(n)$. We look through every node in the tree.

Space Complexity $O(n)$. We store an array with all the values.

Mark as Completed: