LESSON 327 OF 415 · BINARY TREES

Post Order Tree Traversal in Swift: Recursive DFS

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

Example:

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

Output: [3,2,1]

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

STEP 1 OF 7

Guided

Ctrl + Enter to check

SWIFT · BINARY TREES

Post Order Tree Traversal in Swift, explained

Problem overview

The method postOrderTraversal receives the root of a binary tree, as a TreeNode?, and returns the node values in post order: the whole left subtree first, then the whole right subtree, and the node itself last. An empty tree is nil and gives an empty array.

In the example, the tree has root 1 with only a right child, 2, and that node has a left child, 3. The traversal reaches 3 first because it is the deepest node on the left of 2. Then it finishes 2, then 1. The result is [3, 2, 1].

Approach: let recursion do the walking

A tree is a node with two smaller trees below it, and each of those has the same shape. Post order is defined the same way: traverse the left tree, traverse the right tree, then record the node. That definition turns directly into a recursive function.

The function needs a place to put values. Instead of building and merging an array in every call, one array is shared by all calls: the main method creates it, passes it down, and every call appends to it. The order of the appends is the traversal order. The only decision per call is the moment of appending, and doing it after both recursive calls is what makes it post order. Appending first would give pre order, and appending between the two calls would give in order.

On the example, the call for node 1 has no left child, so its first recursive call returns immediately. The second call, on node 2, first goes left to node 3. Node 3 has no children, so it appends 3. Back in node 2, the right side is empty, so 2 is appended. Back in node 1, the right call is finished, so 1 is appended. The array is [3, 2, 1].

This lesson uses the recursive version. The statement also asks whether it can be done iteratively; the second lesson on this problem does that with an explicit stack.

Step by step

Plan the main method. Declare result as an empty [Int] with var, call the helper dfs(root, &result) and return result. It must be a var because the helper changes it.
Declare the helper dfs with two unlabeled parameters: _ root: TreeNode? and _ result: inout [Int].
Stop on an empty subtree. If root is nil, return. This is the base case that ends every branch of the recursion, including calls on missing children.
Recurse left with root!.left, passing &result. The ! is safe because the check above already returned for nil.
Recurse right with root!.right in the same way.
Append the node's value with result.append(root!.val), after both subtrees are done.

The solution in Swift

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

Swift details worth a closer look:

Why inout. Arrays are value types, so a normal array parameter is a constant copy. An inout parameter is written back to the caller's variable when the function returns. Because every recursive call passes the same result with &, they all append to one array.
The & at the call. Swift requires it for inout arguments, and the argument must be a var. A let array can't be passed this way.
Unlabeled parameters. The _ before each name lets callers write dfs(root, &result) instead of dfs(root: root, result: &result).
Optionals. A child may be missing, so left and right are TreeNode?. Comparing an optional with nil works for any type. After the check, root! unwraps it. Unwrapping a nil would crash, and the early return is what prevents that.
Calling a method from a method. Inside the class, dfs is called without self.. Swift looks the name up in the class.

Complexity

Let n be the number of nodes and h the height of the tree.

Time: O(n). Each node gets one call that does the work, plus one cheap call for each missing child, which returns at once. The number of calls is at most about 2n + 1, and each does a constant amount of work. append adds to the end of an array in amortized constant time.

Space: O(h) for the calls, plus O(n) for the result. The recursion is as deep as the tree is tall. That is about log n for a balanced tree and n for a tree that is a single chain. The result array holds all n values.

Edge cases and common mistakes

An empty tree. nil hits the base case at once and the method returns [].
A single node. Both child calls return immediately and the result is just that node's value.
Appending too early. Placing result.append before the recursive calls gives pre order. For the example tree that is [1, 2, 3].
Swapping left and right. Recursing right first would give a mirrored traversal. For the example tree the order would be the same, so test with a tree that has two children.
Forgetting the nil check. Without it, root!.left on a missing child crashes the program.
Forgetting & or inout. The compiler reports an error: without inout, the helper can't modify result, and without & the call doesn't match the declaration.
Very deep trees. Every level costs a stack frame. A tree shaped like a very long chain can exhaust the call stack, which is the reason to learn the iterative version.

Testing

The tree [1, null, 2, 3] gives [3, 2, 1].
An empty tree gives [].
The single node [1] gives [1].
The tree [1, 2, 3, 4, 5] gives [4, 5, 2, 3, 1].

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free