Inverting a Binary Tree with Scala
The problem of Inverting a Binary Tree has got some hype after following tweet.
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
— Max Howell (@mxcl) June 10, 2015
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, we'll see how to solve it using functional programming with 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 the following signature.
$$invertTree: Tree => Tree$$
Solution
First, we define a Binary Tree ADT.
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 notably demonstrates the application of structural recursion generically (e.g., with fold), which is the essence of #fp, imho ;).
If you have any questions, suggestions, or alternative ideas to solve this problem, please feel free to post them as comments; I would greatly appreciate it! Thanks for visiting!
Comments ()