# Inverting a Binary Tree with Scala

The problem of Inverting a Binary Tree has got some hype after following tweet.

As a problem-solver, I was wondering how to approach this problem, as it seems to be a great application of structural recursion. In this post, let’s see how to solve it with functional programming and Scala.

## Problem Definition:

The problem can be specified as follows.

Given a Binary Tree `t1`:

We have to implement a function to transform `t1` to a Binary Tree `t2`:

Thus the function `invertTree` essentially has following signature.

$invertTree: Tree => Tree$

## Solution

First, we define a Binary Tree ADT.

In order to conveniently encode tree instances, we add following methods in the companion object of `Tree`.

As a result, we can define an instance of a tree in Scala REPL as follows.

Next, in order to facilitate structural recursion, we define `fold` function for the binary tree as follows:

It allows to traverse the tree, perform transformations and accumulate the result. For instance, we can define a function to count the length of the tree in a generic manner–

Also, we can define a `map` function that applies a function `f: A ⇒ B` on the `value` of each `Node`. Note that the application of `map` is always structure-preserving, that is, it retains the existing shape as it was before application (unlike the aforementioned `size` function) and perform only local transformations.

As you have guessed, we can similarly define the `invertTree` function in a generic manner as follows:

In essence, `invertTree` simply swaps `left` node with the `right` node, and thus derives the resultant tree with the generic `fold`.

Neat..uh? By the way, this problem can be solved in several ways. This post particularly demonstrates the application of structural recursion in a generic manner (e.g., with `fold`), which is the essence of #fp, imho ;).

If you have any question/suggestion or a different idea to solve this problem, please free to post it as a comment; I highly appreciate that! Thanks for visiting!