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.
The problem can be specified as follows.
Given a Binary Tree
We have to implement a function to transform
t1 to a Binary Tree
Thus the function
invertTree essentially has following signature.
First, we define a Binary Tree ADT.
In order to conveniently encode tree instances, we add following methods in the companion object of
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:
invertTree simply swaps
left node with the
right node, and thus derives the resultant tree with the generic
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!