Problem overview
The method levelOrderTraversal receives the root of a binary tree and returns its values grouped by level, from the root downwards and from left to right within each level, as a [[Int]].
In the example, 3 is the root, 9 and 20 are its children, and 15 and 7 are the children of 20. The levels are [3], [9, 20] and [15, 7], so the answer is [[3], [9, 20], [15, 7]]. An empty tree has no levels and returns [].
Approach: carry the level down the recursion
The usual way to read a tree level by level is a queue, which visits nodes in exactly that order. This lesson takes another route: an ordinary depth-first recursion that remembers each node's depth. A node's level is its parent's level plus one, so passing level + 1 to the recursive calls is enough. Each node is appended to the list for its own level, so it doesn't matter that the recursion goes deep before it goes wide.
Left-to-right order inside a level comes for free. The recursion always finishes the whole left subtree before it starts the right one, so for any level, nodes that are further left are visited first.
The only bookkeeping is creating each level's list at the right moment. A depth-first walk reaches level k for the first time only after it has been through levels 0 to k - 1, because it has to pass through their nodes to get there. So whenever level is equal to result.count, the level is new and needs an empty list.
Tracing the example
The first call visits 3 on level 0. result is empty, so a list is created and 3 goes into it. The left call visits 9 on level 1: a second list is created and 9 is added. 9 has no children, so both of its calls return at once. Back at 3, the right call visits 20 on level 1. That list already exists, so 20 joins 9. Then 15 and 7 are visited on level 2, and the third list is created for 15. The result is built level by level even though the walk went deep first.
Step by step
- Declare
resultas avar. It starts as an empty[[Int]], andresult[level]will hold the values of that level. - Call
dfson the root with level 0 and&result. The helper is written afterwards; the&passes the array as aninoutargument. - Return
result. - Declare
dfsabove the main method, with the parametersroot,levelandresult, all unlabelled.resultisinoutbecause arrays are values in Swift, and a function would otherwise change only its own copy. - Return on
nil. A missing child ends the recursion. - Create the level when it is new. If
level >= result.count, this is the first node reached on this level, so append an empty[Int](). - Append the node's value to
result[level].rootis still optional, soroot!unwraps it, which is safe after thenilcheck. - Recurse left, then right, both with
level + 1. Going left first keeps every level in left-to-right order.
The solution in Swift
class Solution {
func dfs(_ root: TreeNode?, _ level: Int, _ result: inout [[Int]]) {
if root == nil {
return
}
if level >= result.count {
result.append([Int]())
}
result[level].append(root!.val)
dfs(root!.left, level + 1, &result)
dfs(root!.right, level + 1, &result)
}
func levelOrderTraversal(_ root: TreeNode?) -> [[Int]] {
var result = [[Int]]()
dfs(root, 0, &result)
return result
}
}
Swift details worth knowing:
- Nested arrays are values.
result[level].append(...)modifies the inner array insideresultin place. It doesn't copy the inner array into a temporary and lose the change. - Indexing out of range crashes. Reading or writing
result[level]before that list exists stops the program. The check that appends the empty list is what makes the next line safe. inout. Every recursive call passes&result, so all calls fill the same array.
Complexity
Time: O(n), where n is the number of nodes. Each node is visited once and appended once, and every nil child adds one call that returns at once.
Space: O(n) for the result, plus O(h) for the call stack, where h is the tree's height. For a balanced tree h is about log n; for a tree that is one long chain, h equals n.
Edge cases and common mistakes
- Empty tree. The first call returns at the
nilcheck, soresultstays[]. - Single node. The tree
[1]returns[[1]]. - Skewed tree. A tree where every node has only a left child gives one value per level:
[[1], [2], [3]]. - Adding the level list too late. Appending to
result[level]before the new-level check crashes the first time a level is reached. - Visiting the right child first. Each level would come out reversed.
- Forgetting
level + 1. Passing the samelevelto the children puts every node on level 0.
Testing
- The tree
[3, 9, 20, null, null, 15, 7]gives[[3], [9, 20], [15, 7]]. - An empty tree gives
[]. - The tree
[1, 2, 3, 4, null, null, 5]gives[[1], [2, 3], [4, 5]].
