Level Order Traversal

#70 · Trees · Intermediate · 65 XP · about 10 min

Write levels(root) that returns the values of a binary tree level by level: a list with one inner list per level, starting at the root, where each inner list goes from left to right. An empty tree gives [].

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

levels(build([4, 1, 7, None, None, 5, 9]))  # returns [[4], [1, 7], [5, 9]]
levels(build([1, 2, 3, 4, None, None, 5]))  # returns [[1], [2, 3], [4, 5]]
levels(build([]))  # returns []

The drawing shows the first tree. In the second example 4 and 5 are on the same level even though they have different parents.

Constraints

0 to 2,000 nodes; values are integers, including 0 and negative numbers.

# Provided: do not change

from collections import deque

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

def build(values):

"""Build a tree from a level-order list; None marks a missing child."""

if not values or values[0] is None:

return None

root = Node(values[0])

queue = deque([root])

i = 1

while queue and i < len(values):

node = queue.popleft()

if values[i] is not None:

node.left = Node(values[i])

queue.append(node.left)

i += 1

if i < len(values) and values[i] is not None:

node.right = Node(values[i])

queue.append(node.right)

i += 1

return root

def levels(root):

# Your code here

pass

print(levels(build([4, 1, 7, None, None, 5, 9])))

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.