Write a function that returns a tree's values level by level: a list of lists, where the first list holds the root's value, the next holds the values one level down (left to right), and so on. An empty tree gives an empty list.
Write values_by_level(root) in Python or valuesByLevel(root) in JavaScript. Examples are written in Python: in JavaScript, None is null and True / False are true / false.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 16 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Which traversal?
"Level by level" is breadth-first: visit everything at depth 0, then depth 1, and so on. Breadth-first search uses a queue.
Step 2
Know where each level ends
A plain BFS gives the values in the right order, but mixed together. At the start of each level, the queue holds exactly that level's nodes. Read the queue's length then, and process exactly that many nodes before starting the next list.
Step 3
Process one level
For each of those nodes: add its value to the current level's list, and put its children (left, then right) at the back of the queue. They'll form the next level.
Step 4
A depth-first alternative
You can also do a DFS that passes the depth down, appending each value to levels[depth]. Visiting left before right keeps each level in order.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Start a queue with the root (if there is one). While the queue isn't empty, take its current size, pop that many nodes into a new list while queueing their children, and add the list to the answer.
python
1from collections import deque
2
3
4def values_by_level(root):
5 if root is None:
6 return []
7 levels = []
8 queue = deque([root])
↑start with level 1: just the root
9 while queue:
10 level = []
11 for _ in range(len(queue)): # exactly the nodes on this level
↑exactly the nodes on this level
12 node = queue.popleft()
13 level.append(node.val)
14 if node.left:
15 queue.append(node.left)
↑children form the next level
16 if node.right:
17 queue.append(node.right)
18 levels.append(level)
↑one level done
19 return levels
javascript
1function valuesByLevel(root) {
2 if (!root) return []
3 const levels = []
4 let queue = [root]
↑start with level 1: just the root
5 while (queue.length) {
6 const next = []
7 levels.push(queue.map((node) => node.val)) // exactly the nodes on this level
↑exactly the nodes on this level
8 for (const node of queue) {
9 if (node.left) next.push(node.left)
↑children form the next level
10 if (node.right) next.push(node.right)
11 }
12 queue = next
↑one level done
13 }
14 return levels
15}
Complexity
TimeO(n)SpaceO(w)
O(n) time: every node is queued and processed once. O(w) extra space for the queue, where w is the widest level (up to about n/2 in a full tree).
What we learned
Snapshot the queue's length to separate one level from the next.
Use collections.deque in Python (or a head index in JavaScript) so taking from the front is O(1).
BFS space depends on the tree's width; DFS space depends on its height.