Problem overview
The method levelOrderTraversal receives the root of a binary tree of TreeNode objects and returns an Array[Array[Int]]. Each inner array holds the values of one level of the tree, from left to right. The root is level 0, its children are level 1, and so on.
For the tree with root 3, children 9 and 20, and 20's children 15 and 7, the result is [[3], [9, 20], [15, 7]]. An empty tree gives an empty array.
Approach: carry the level down the recursion
The usual way to read a tree level by level is breadth-first search with a queue. This lesson reaches the same result with an ordinary recursive depth-first walk, by passing along the current level number.
The result is a buffer of buffers, and result(level) collects the values of that level. When the walk reaches a node at depth level, it appends the node's value to result(level). The walk visits the left child before the right child, so within any one level the nodes arrive from left to right, and the values end up in the order the problem wants.
Only one thing needs care: the inner buffer for a level must exist before the first value is added. Because the walk goes down the left side first, the first node to reach a new depth is always one past the last existing level, so a single check level >= result.length detects it.
In the example, the walk visits 3 (level 0), 9 (level 1), 20 (level 1), 15 (level 2) and 7 (level 2). Each value lands in its level's buffer in that order. The walk visits nodes in preorder, but the output is grouped by level.
Step by step
- Create
resultas an emptyArrayBufferwhose elements areArrayBuffer[Int], withval. It can grow whenever the walk goes deeper. The code writes the full pathscala.collection.mutable, so no import is needed. - Start the walk by calling
dfs(root, 0, result). The root sits at level 0. - Return the converted result.
result.map(_.toArray).toArrayturns each inner buffer into an array and then the outer buffer into an array. - Declare
dfsabovelevelOrderTraversal, with the node, its level and the shared buffer as parameters, returningUnit. - Stop at
null. An empty subtree has no values, so the call returns. - Create the level's buffer when needed. If
level >= result.length, append an emptyArrayBuffer[Int]()toresult. - Append the value with
result(level) += root.value. - Recurse left, then recurse right, both with
level + 1. The left-before-right order keeps every level sorted from left to right.
The solution in Scala
class Solution {
def dfs(root: TreeNode, level: Int, result: scala.collection.mutable.ArrayBuffer[scala.collection.mutable.ArrayBuffer[Int]]): Unit = {
if (root == null) {
return
}
if (level >= result.length) {
result += scala.collection.mutable.ArrayBuffer[Int]()
}
result(level) += root.value
dfs(root.left, level + 1, result)
dfs(root.right, level + 1, result)
}
def levelOrderTraversal(root: TreeNode): Array[Array[Int]] = {
val result = scala.collection.mutable.ArrayBuffer[scala.collection.mutable.ArrayBuffer[Int]]()
dfs(root, 0, result)
result.map(_.toArray).toArray
}
}
The Scala details worth a closer look:
- Two meanings of
+=on one line pair.result += scala.collection.mutable.ArrayBuffer[Int]()appends a new empty buffer to the outer buffer.result(level) += root.valuefirst looks up the inner buffer with round brackets and then appends anIntto it. valfixes the name, not the contents.resultis aval, and the buffers it holds still change. That is also whydfscan fill a buffer that its caller created.- Why convert at the end. The method promises
Array[Array[Int]]. Buffers are used while the size is unknown, andmap(_.toArray)followed bytoArraydoes the conversion once the walk is finished. - The last expression is the return value.
result.map(_.toArray).toArrayneeds noreturn. The onlyreturnin the code is the early exit fromdfs. nullmarks a missing child in this lesson'sTreeNode, so the base case comparesrootwithnull.
Complexity
Time: O(n) for n nodes. Each node is visited once, and a missing child costs one extra call that returns at once. Appending to a buffer is constant time on average.
Space: O(n) for the result, plus O(h) for the call stack, where h is the tree's height. A queue-based search would instead keep up to one level of nodes in memory and avoid deep recursion, which is the better choice for very deep trees.
Edge cases and common mistakes
- Empty tree. A
nullroot returns at once, soresultstays empty and the method returns an empty array. - Gaps in the tree. Root 1 with left child 2 (which has only a right child 4) and right child 3 gives
[[1], [2, 3], [4]]. Missing nodes leave no placeholders. - Visiting right before left. That would put every level in right-to-left order, so the example would give
[[3], [20, 9], [7, 15]]. - Skipping the new-level check. Calling
result(level)on a level that has no buffer yet throws anIndexOutOfBoundsException. - Using
==instead of>=in that check. The walk never skips a level, so==would also work for this traversal, but>=states the intent more clearly and is safe if the order of visits changes. - Passing
levelinstead oflevel + 1to the children. Every node would then land on the same level as its parent. - Appending the empty buffer in the wrong place. Appending it on every call, instead of only on the first visit to a level, produces one extra empty array per node.
Testing
- Root 3 with children 9 and 20, and 20's children 15 and 7, gives
[[3], [9, 20], [15, 7]]. - A
nullroot gives[]. - Root 1 with left child 2 (whose right child is 4) and right child 3 gives
[[1], [2, 3], [4]].
