Recursion

Breadth First Traversal

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:

treeLayers(TreeNode.of([1, 2, 3, 4, 5, None, 6]))
# [[1], [2, 3], [4, 5, 6]]

treeLayers(TreeNode.of([1, 2, 3]))
# [[1], [2, 3]]

treeLayers(TreeNode.of([1, 2, 3, 4, 5, 6, 7]))
# [[1], [2, 3], [4, 5, 6, 7]]

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:

from collections import deque

def treeLayers(root):
    soln = []
    queue = deque([root])
    while queue:
        layer = []                  # create layer
        for _ in range(len(queue)): 
            node = queue.popleft()
            layer.append(node.val)  # add value to layer
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        soln.append(layer)          # add layer to soln
    
    return soln

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:

Submits:

treeLayers

Imports:

TreeNode

Test your code to get an output here!

treeLayers(

)

Test your code to get an output here!