 Given the root node of a binary tree `root`, return an array containing the Breadth-First traversal of the tree. Example: 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 (see the previous lesson for a derivation): ``` queue = deque([root]) while queue: loop through nodes in current layer for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(n

Breadth First Traversal



-----problem-----



    Given the root node of a binary tree `root`, return an array containing the Breadth-First traversal of the tree. 


    \b{Example:}
   \image{0}

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



-----solution-----


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 (see the previous lesson for a derivation):


```
queue = deque([root])
while queue:
    # loop through nodes in current layer
    for _ in range(len(queue)):
        node = queue.popleft()
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

```


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:


\answer

\tc $O(n)$. We look through every node in the tree.

\sc $O(n)$. We store an array with all the values.


Recursion

Breadth First Traversal