How to Invert a Binary Tree in Swift

In my last post I showed how to solve one of the classic whiteboard interview problems: reversing a linked list. In this post I will explore the similar but slightly more challenging problem of how to invert a binary tree. Once again I will be using Swift 3 to write the code.


A binary tree can be thought of as a series of nodes, each of which has a value as well as up to two child nodes. We will call the children the left branch and the right branch.

A leaf node is a special node that has only a value. It marks the end of the tree.

We will also define an empty node that contains no value and no branches. We will use this to indicate when a node is missing a branch. This way, we don’t have to make the branch an optional value.

Here’s what our binary tree will look like in Swift.

public enum BinaryTree<T> {
case empty
case leaf(value: T)
indirect case node(
value: T, left: BinaryTree<T>, right: BinaryTree<T>)
}

This should look similar to how we defined the linked list data structure.


Now can write a function to invert a binary tree. To invert the tree, we are going to swap the left and right branches of each node in the tree. This will effectively transform the tree into its mirror image.

public func inverted() -> BinaryTree<T> {
switch self {
case .empty:
return .empty
case .leaf(let value):
return .leaf(value: value)
case .node(let value, let left, let right):
return .node(value: value,
left: right.inverted(),
right: left.inverted())
}
}

Just like reversing a linked list, this is a straightforward recursive transformation.


All that’s left now is to show our new function in action.

Because it can be a little difficult to visualize the tree, we will create a custom description property that will recursively descend the tree and construct a representation of its values.

extension BinaryTree: CustomStringConvertible {
public var description: String {
switch self {
case .empty:
return "()"
case .leaf(let value):
return "\(value)"
case .node(let value, let left, let right):
return "(\(left) <- \(value) -> \(right))"
}
}
}

To exercise the inverting method, let’s construct a tree with the numbers 1 through 6 added in sorted order. After inverting the tree, we should find that the values are now in descending order!

let tree: BinaryTree<Int> = .node(
value: 4,
left: .node(
value: 2,
left: .leaf(value: 1),
right:.leaf(value: 3)),
right: .node(
value: 6,
left: .leaf(value: 5),
right: .empty))
print(tree)
// ((1 <- 2 -> 3) <- 4 -> (5 <- 6 -> ()))
print(tree.inverted())
// ((() <- 6 -> 5) <- 4 -> (3 <- 2 -> 1))
Like what you read? Give Robert Cottrell a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.