## 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).