Start learning free

LESSON 335 OF 415 · BINARY TREES

Inorder Traversal in Swift: Recursive Depth-First Search

Practice O(n) Read the full explanation

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

Example:

Input: [1,nil,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

    SWIFT · BINARY TREES

    Inorder Traversal in Swift, explained

    Problem overview

    The method inorderTraversal receives the root of a binary tree, as a TreeNode?, and returns the values of all nodes as an [Int] in inorder: for every node, first everything in its left subtree, then the node itself, then everything in its right subtree.

    In the example, node 1 has no left child and a right child 2, and node 2 has a left child 3. Starting at 1, the left subtree is empty, so 1 comes first. Next comes the right subtree, rooted at 2: its left subtree holds 3, so 3 comes before 2. The result is [1, 3, 2].

    Approach: let recursion follow the shape of the tree

    A tree is defined in terms of smaller trees: each child is the root of a subtree. The inorder rule is defined the same way, so a recursive function fits it directly. To traverse a subtree, traverse its left subtree, record the root, then traverse its right subtree. An empty subtree, a nil child, records nothing and ends the recursion.

    The statement suggests an iterative version as a follow-up. This lesson uses the recursive one, which is the shortest way to see the pattern. The other two depth-first orders only change where the "record" line sits: before the two recursive calls gives preorder, after them gives postorder.

    Step by step

    1. Declare the helper dfs. It takes the subtree's root and the array being filled. The array is an inout parameter, because Swift arrays are values: without inout the function would receive its own copy, and nothing it appended would reach the caller. Both parameters use _, so calls need no argument labels.
    2. Stop on nil. A missing child is an empty subtree and adds nothing. This check is the base case that ends every branch of the recursion.
    3. Recurse into the left subtree with root!.left and &result. The ! is safe because the check above already returned when root was nil, and & is required at every call that passes an inout argument.
    4. Append root!.val. By now every value from the left subtree is in the array, so the current node lands right after them.
    5. Recurse into the right subtree the same way. Left subtree, node, right subtree: that order defines inorder.
    6. In inorderTraversal, declare result with var. A constant can't be passed as an inout argument.
    7. Call dfs(root, &result) to fill it, then return result.

    The solution in Swift

    class Solution {
    func dfs(_ root: TreeNode?, _ result: inout [Int]) {
        if root == nil {
            return
        }
        dfs(root!.left, &result)
        result.append(root!.val)
        dfs(root!.right, &result)
    }
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        dfs(root, &result)
        return result
    }
}

    The Swift details worth a closer look:

    • inout and &. An inout parameter is copied in, changed, and copied back out when the function returns. The compiler optimises this so the array isn't actually duplicated at each call, and the recursive calls all work on the same result.
    • Optionals. left and right are TreeNode?, so a missing child is nil. Comparing with root == nil is allowed even though TreeNode isn't Equatable, and force-unwrapping with ! would crash on nil, which is why the check comes first. An alternative is guard let root = root else { return }, which unwraps once and removes every !.
    • Classes are references. TreeNode is a class, so passing a node to dfs passes a reference. The array, a value type, needed inout; the nodes didn't.

    Complexity

    Time: O(n), where n is the number of nodes. Each node is visited once, and each visit does a constant amount of work: one append and two calls. Every nil child costs one extra call that returns immediately, which at most doubles the number of calls.

    Space: O(h) for the call stack, where h is the height of the tree, on top of the O(n) result. A balanced tree has h around log n. A tree that is a single chain has h = n, and a chain of millions of nodes could exhaust the stack. An iterative version with an explicit stack avoids that limit.

    Edge cases and common mistakes

    • Empty tree. A nil root returns [].
    • Single node. The tree [5] returns [5].
    • Appending in the wrong place. Putting the append before the left call gives preorder, [1, 2, 3] for the example; putting it last gives postorder, [3, 2, 1].
    • Forgetting &. The compiler rejects a call that passes an array to an inout parameter without it.
    • Declaring result with let. A constant can't be passed with &, so the code doesn't compile.
    • Checking only the root's children. The base case belongs at the top of dfs, so every nil is handled in one place.

    Testing

    • The tree [1, null, 2, 3] gives [1, 3, 2].
    • An empty tree gives [].
    • The perfect tree [4, 2, 6, 1, 3, 5, 7], a binary search tree, gives [1, 2, 3, 4, 5, 6, 7]: the inorder traversal of a binary search tree is sorted.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free