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.

## 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!