## 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`:

 4 / \ 2 7 / \ / \ 1 3 6 9
view raw actual-tree.txt hosted with ❤ by GitHub

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

 4 / \ 7 2 / \ / \ 9 6 3 1
view raw invertedTree.txt hosted with ❤ by GitHub

Thus the function `invertTree` essentially has following signature.

$invertTree: Tree => Tree$

## Solution

First, we define a Binary Tree ADT.

 sealed trait Tree[+A] case object EmptyTree extends Tree[Nothing] case class Node[A](value: A , left: Tree[A], right: Tree[A]) extends Tree[A]
view raw BinaryTree.scala hosted with ❤ by GitHub

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

 object Tree{ def empty[A]: Tree[A] = EmptyTree def node[A](value: A, left: Tree[A] = empty, right: Tree[A] = empty): Tree[A] = Node(value, left, right) }
view raw BinaryTree.scala hosted with ❤ by GitHub

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

 scala> val t1 = node(4, node(2 , node(1) , node(3) ) , node(7 , node(6) , node(9) ) ) t1: Tree[Int] = Node(4, Node(2, Node(1,EmptyTree,EmptyTree), Node(3,EmptyTree,EmptyTree)), Node(7, Node(6,EmptyTree,EmptyTree), Node(9,EmptyTree,EmptyTree)))
view raw BinaryTree.scala hosted with ❤ by GitHub

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

 def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B): B = t match { case EmptyTree => z case Node(x,l,r) => f ( fold( l , z )(f) , x , fold( r , z )(f) ) }
view raw fold.scala hosted with ❤ by GitHub

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–

 def size[T] (tree: Tree[T]) = fold(tree, 0: Int){(l,x,r) => l + r + 1} scala> size(t1) res11: Int = 7
view raw BinaryTree.scala hosted with ❤ by GitHub

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.

 import Tree._ def map[A,B](tree: Tree[A])(f: A => B): Tree[B] = fold(tree, Tree.empty[B]){(l, x, r) => Node(f(x), l,r)} scala> map (t1) ( x => x * 10) res11: Tree[Int] = Node(40, Node(20, Node(10,EmptyTree,EmptyTree), Node(30,EmptyTree,EmptyTree)), Node(70, Node(60,EmptyTree,EmptyTree), Node(90,EmptyTree,EmptyTree)))
view raw BinaryTree.scala hosted with ❤ by GitHub

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

 def invertTree[A](tree: Tree[A]): Tree[A] = fold (tree, Tree.empty[A]){(leftT, value, rightT) => Node(value, rightT, leftT)}
view raw BinaryTree.scala hosted with ❤ by GitHub

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

 scala> invertTree(t1) res12: Tree[Int] = Node(4, Node(7, Node(9,EmptyTree,EmptyTree), Node(6,EmptyTree,EmptyTree)), Node(2, Node(3,EmptyTree,EmptyTree), Node(1,EmptyTree,EmptyTree))) /* 4 / \ 7 2 / \ / \ 9 6 3 1 */
view raw BinaryTree.scala hosted with ❤ by GitHub

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!

## Gist: JAVA 8 Stream API: Stream Initialization

Stream represents a sequence of values. Stream API, introduced in JAVA 8 (JSR-355 [1]) enables declarative specification of computation on data. It may also interesting to note that it imposes no restriction on the data source.

Following are the important facts:

• Stream != Collection
• It is bound to a data source which can be {collection, array, IO, iterator}
• Stream does not hold any data
• It is simply an intermediate data
• Stream can’t modify its source
• Good for parallelism.
• Stream can be infinite.

In this post, we only discuss how to construct a `Stream` object.

A `Stream` object can be constructed in the following manner.

```    Collection source = /*a collection that will be used as a source of Stream*/

source.stream();
```

Alternatively, `Stream` contains several builders, as listed below.

• IntStream: `Stream.of(1,3,4)`
• EmptyStream: `Stream.empty()`
• InfiniteStream: `Stream.iterate(1, n-&gt; n+10)`

In the next post, we shall discuss more on how we can use a `Stream` to specify data transformation in a declarative manner.

# References:

## Certificate of #ProgFun of @Coursera

Yay! Finally, I have received the certificate of Functional Programming Principles in Scala course. Thanks @coursera! It has been a great pleasure, and I look forward to the future courses (e.g., Discrete Optimization).

In a previous post, I remember mentioning how awesome this course is, and how much I have enjoyed this course, and looking forward to the next advanced course in this topic. It’s great to know that around 70% students ‘Absolutely’ share the same feeling. So, prof. @oderskey, please hurry up. We are waiting!

Once again, thanks prof. @oderskey and his team for this excellent course.

## Retrospective of #ProgFun

Yay! Just finished Functional Programming Principles in Scala (with 100% score :D) instructed by Prof. Martin Odersky et al, at Coursera. It has been an excellent experience due to its great content, amazing teacher, and interesting assignments (e.g., implementing a solver for Bloxorz).

This course focuses on providing a deeper understanding of FP paradigm, and demonstrates how it excels elegantly compare to its contemporaries. Function composition, recursion, pattern matching, concepts of persistent data structures, lazy evaluation are among the few important concepts that have been emphasized and exemplified in the seven weeks of the course. The application of term-rewriting during reduction of expressions and reasoning about it, seemed simply awesome.

Overall, it has been a wonderful experience and I highly recommend it for anyone interested in learning FP paradigm. To motivate further, note that upon successful completion, a certificate from Coursera is provided ;).

Thanks @oderskey, his team, and @coursera for this excellent course, and for this great opportunity. Looking forward to its advanced part.

## Scala Hacking: Computing Powerset

Given a set represented as a `String`, we can compute its powerset using `foldLeft`, as shown below.

 def powerset(s: String) = s.foldLeft(Set("")) { case (acc, x) => acc ++ acc.map(_ + x) }
view raw powerset.scala hosted with ❤ by GitHub

Isn’t this approach quite concise and elegant? Following snippet shows a pretty-printed output from `powerset` for a set: `"abc"`.

```scala> powerset("abc").toList sortWith ( _ < _) mkString "\n"

res3: String = "
| a
| ab
| abc
| ac
| b
| bc
| c"```

Following is a F# implementation of this same function.

 let powerset (s:string): Set = s.ToCharArray() |> Array.fold( fun (acc: Set) x -> acc + (Set.map(fun y -> x.ToString()+y) acc) ) (Set.empty.Add(""))
view raw powerset.fs hosted with ❤ by GitHub