Start learning free

LESSON 311 OF 348 · BINARY TREES

Level Order Traversal in Kotlin: Depth-First Search by Level

Practice O(n) Read the full explanation

Given a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example:

Input: [3, 9, 20, null, null, 15, 7]
    3
   / \
  9  20
    /  \
   15   7

Output: 
[
  [3],
  [9, 20],
  [15, 7]
]

STEP 1 OF 9
    Ctrl + Enter to check

    KOTLIN · BINARY TREES

    Level Order Traversal in Kotlin, explained

    Problem overview

    The function levelOrderTraversal receives the root of a binary tree, a TreeNode?, and returns a List<List<Int>>. Each inner list holds the values of one level of the tree, from left to right, and the outer list goes from the root's level downward.

    In the example, 3 is the root, 9 and 20 are its children, and 15 and 7 are the children of 20. The answer is [[3], [9, 20], [15, 7]]. An empty tree gives an empty list.

    Approach: remember each node's level

    The usual way to traverse level by level is breadth-first search with a queue. This lesson uses a different idea that needs no queue: do an ordinary depth-first traversal, but pass each node's level down the recursion. The root is on level 0, its children on level 1, and in general a child is one level deeper than its parent.

    The result is a list of lists where result[level] collects the values on that level. When a node on level level is reached, its value is appended to result[level]. If the traversal has never been that deep before, that inner list doesn't exist yet, so it is created first.

    Order within a level comes from visiting the left child before the right child. Two nodes on the same level are reached in left-to-right order, because the traversal enters the left subtree completely before the right one.

    The queue-based version visits nodes in true level order and needs extra memory for a whole level at once. The depth-first version visits nodes in a different order but still fills every level correctly, and it takes only a few lines because the recursion does the bookkeeping.

    Step by step

    1. Create result as an empty MutableList<MutableList<Int>> with mutableListOf. The outer list will gain one inner list per level.
    2. Call dfs(root, 0, result), assuming the helper exists. The root's level is 0.
    3. Return result.
    4. Declare dfs above levelOrderTraversal with the parameters root: TreeNode?, level: Int and result. It returns nothing.
    5. Return on a null root. A missing child has no values. Afterwards Kotlin smart-casts root to a non-null TreeNode.
    6. Create the level if it is new. When level >= result.size, the traversal has just reached a depth it hasn't seen, so add an empty inner list. Because the traversal goes down one level at a time, level can be at most result.size, so one added list is always enough.
    7. Add root.value to result[level].
    8. Recurse on root.left with level + 1.
    9. Recurse on root.right with level + 1, after the left one so each level stays ordered left to right.

    The solution in Kotlin

    class Solution {
    fun dfs(root: TreeNode?, level: Int, result: MutableList<MutableList<Int>>) {
        if (root == null) {
            return
        }
        if (level >= result.size) {
            result.add(mutableListOf())
        }
        result[level].add(root.value)
        dfs(root.left, level + 1, result)
        dfs(root.right, level + 1, result)
    }

    fun levelOrderTraversal(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        dfs(root, 0, result)
        return result
    }
}

    On the example, the calls run in this order: 3 creates level 0; 9 creates level 1; 20 is added to level 1; 15 creates level 2; 7 is added to level 2. Level 1 receives 9 before 20 even though 9's subtree is finished first, which shows why a depth-first walk still produces left-to-right levels.

    The Kotlin details worth a closer look:

    • Type inference in result.add(mutableListOf()). The empty list has no elements to infer a type from, but result is a list of MutableList<Int>, so the compiler fills in mutableListOf<Int>() from the context.
    • Indexing with result[level]. This is shorthand for result.get(level). It throws IndexOutOfBoundsException when the level doesn't exist yet, which is why the if comes first.
    • Nested mutable types. The helper needs MutableList<MutableList<Int>> so that it can both add levels and add values to them. The function returns it as List<List<Int>>, which Kotlin accepts because its read-only list types are covariant.

    Complexity

    Time: O(n) for n nodes. Each node is visited once and does a constant amount of work, and each missing child costs one call that returns immediately.

    Space: O(n) for the result, plus O(h) for the recursion, where h is the height of the tree. The recursion is deepest for a tree that is one long chain, where h = n.

    Edge cases and common mistakes

    • Empty tree. null returns [], because no level is ever created.
    • Single node. A root of 5 returns [[5]].
    • Lopsided trees. Node 1 with left child 2 (which has left child 3) and right child 4 returns [[1], [2, 4], [3]]. Level 2 is created while following the left side, long before the right side is visited.
    • Checking level == result.size versus >=. Both work here, since a level can never skip ahead. >= is the safer habit.
    • Visiting right before left. Every level would come out reversed.
    • Forgetting level + 1. Passing level unchanged puts every value on level 0.

    Testing

    • The example tree gives [[3], [9, 20], [15, 7]].
    • A single node 5 gives [[5]].
    • null gives [].
    • Node 1 with left child 2 (which has left child 3) and right child 4 gives [[1], [2, 4], [3]].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free