Start learning free

LESSON 310 OF 348 · BINARY TREES

Inorder Traversal in Kotlin: Recursive Binary Tree DFS

Practice O(n) Read the full explanation

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1, 3, 2]

Follow up: Recursive solution is trivial, could you do it iteratively?

STEP 1 OF 8
    Ctrl + Enter to check

    KOTLIN · BINARY TREES

    Inorder Traversal in Kotlin, explained

    Problem overview

    The function inorderTraversal receives the root of a binary tree, a TreeNode?, and returns a List<Int> with the node values in inorder: for every node, the whole left subtree comes first, then the node itself, then the whole right subtree.

    In the example, node 1 has no left child and a right child 2, and node 2 has a left child 3. Inorder visits 1 (nothing on its left), then goes into its right subtree: 3 (the left child of 2), then 2. The result is [1, 3, 2]. An empty tree, where root is null, gives an empty list.

    Approach: recurse left, visit, recurse right

    A tree is a node with two smaller trees hanging off it, and either of them can be empty. That structure fits recursion: the inorder traversal of a tree is the inorder traversal of its left subtree, then the node's value, then the inorder traversal of its right subtree. An empty subtree contributes nothing, which is the base case that stops the recursion.

    Instead of building and joining a new list in every call, the solution passes one list down and every call appends to it. Because the calls happen in inorder, the values land in the list in the right order.

    The statement's follow-up asks for an iterative version, which uses an explicit stack instead of the call stack. This lesson is the recursive one.

    Step by step

    1. Declare the helper dfs above inorderTraversal. It takes a TreeNode? (the subtree's root, which may be null for a missing child) and a MutableList<Int> to fill. It returns nothing, because its work shows up in the list.
    2. Stop on a null root. An empty subtree adds nothing, so the function returns at once. After this check Kotlin treats root as non-null, so the next lines use it without ?. or !!.
    3. Recurse on root.left first, so every value in the left subtree is added before the current node's.
    4. Add root.value to the list. In this lesson's TreeNode, the number is stored in the field value.
    5. Recurse on root.right. Left, node, right is exactly what makes the traversal inorder.
    6. In inorderTraversal, create the list with mutableListOf<Int>(). The element type is written out because an empty list gives Kotlin nothing to infer it from.
    7. Call dfs(root, result) to fill it, and return result.

    The solution in Kotlin

    class Solution {
    fun dfs(root: TreeNode?, result: MutableList<Int>) {
        if (root == null) {
            return
        }
        dfs(root.left, result)
        result.add(root.value)
        dfs(root.right, result)
    }

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

    The Kotlin details worth a closer look:

    • Nullable parameter and smart cast. TreeNode? means the argument can be null. Once the if (root == null) return check has run, the compiler knows root is a real TreeNode for the rest of the function, so root.left and root.value compile. Without the check, root.value is a compile error.
    • val with a mutable list. val result fixes the variable, not the list, so add still works. The helper changes the very list the caller created, because the list is passed by reference.
    • MutableList and List. A plain List<Int> has no add. The helper asks for a MutableList<Int>, and the function returns it as a List<Int>, which is allowed because every MutableList is also a List.
    • Methods can call each other in any order. dfs is written before inorderTraversal, but inside a class the order of member functions does not matter.

    Complexity

    Time: O(n) for n nodes. Each node gets one call that does real work, and each missing child gets one call that returns at once, so the total number of calls is about 2n + 1.

    Space: O(h) extra for the call stack, where h is the height of the tree, plus the O(n) result list. A balanced tree has h near log n. A tree where every node has only a left child has h = n, and a very deep one can overflow the stack: a chain of 20,000 left children made this solution throw StackOverflowError on the JVM's default stack. The iterative version avoids that limit.

    Edge cases and common mistakes

    • Empty tree. null returns [], since the first dfs call returns immediately.
    • Single node. A tree with just the value 5 returns [5].
    • Mixing up the orders. Moving result.add before the left call gives preorder, and moving it after the right call gives postorder. The position of that one line is the only difference between the three traversals.
    • Returning a new list from each call. It works, but it copies lists at every level. Sharing one list avoids that.
    • Using !! to silence the compiler. The null check makes it unnecessary, and !! would throw if a missing child ever reached it.

    Testing

    • Node 1 with right child 2, which has left child 3, gives [1, 3, 2].
    • Node 2 with children 1 and 3 gives [1, 2, 3].
    • null gives [].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free