Inverting a Binary Tree

I start most days a little before the sun comes up with a short run to a nearby park. I usually listen to a podcast or some music.


This morning I dug into to episode #232 of the Changelog, which features an interview with Max Howell. Howell is the creator of HomeBrew, and the tweeter of this now infamous tweet.

Putting aside a lengthy discussion of Google’s interviewing practices, I decided instead to take a few minutes and come up with a binary tree inversion implementation in Swift.

I started with a simple Tree type:

enum Tree<T> {
    case empty
    indirect case cons(Tree, T, Tree)
}


This tree takes a generic type, T, for the value at each node. Branches can be constructed using the recursive cons case and passing in additional subtrees, or Tree.empty (which signifies a terminus).

    func invert() -> Tree {
        switch self {
        case .empty:
            return self
        case .cons(let leftNode, let value, let rightNode):
            return Tree.cons(rightNode.invert(),
                             value,
                             leftNode.invert())
        }
    }


The recursive implementation of the inversion function follows naturally from the recursive Tree implementation. If the tree is at a terminus (.empty), the inversion function simply returns the tree. Otherwise, the inversion function calls itself, passing in a new tree identical to the tree it’s operating on, but with the left and right subtrees swapped.

Since each node in the tree is traversed only once, the time complexity is Θ(n), where n is the number of nodes in the tree.

Because of recursion, Θ(h) function calls will be placed on the stack in the worst case, where h is the height of the tree. h∈O(n), so the space complexity of this implementation is Θ(n).