## Binary tree folding

I have been given the following definition of a binary tree abstract class Tree[+A] case class Leaf[A](value: A) extends Tree[A] case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] and the following function def fold_tree[A,B](f1: A => B)(f2: (A, B, B) => B)(t: Tree[A]): B = t match { case Leaf(value) => f1(value) case Node(value, l, r) => f2(value, fold_tree(f1)(f2)(l), fold_tree(f1)(f2)(r)) //post order } I have been asked to return the rightmost value in the tree using the fold method. How would this work? I'm not sure I fully understand fold, but I thought the point of fold was to do some operation to every element in the tree. How can I use it to just return the rightmost value of a tree? I am also unsure as to how to call the method. I keep getting issues with unspecified parameter type. Can someone show me the proper way to call this fold_tree method?

## Solutions/Answers:

### Answer 1:

How would this work? I’m not sure I fully understand fold

What your `foldTree`

method is doing is recursively walking the tree, applying itself to each `Node`

or `Leaf`

it encounters in the way. The method also has two type parameters that need to be applied, `A`

and `B`

, depending on the type of the provided tree.

Let’s for the sake of the example say we have a `Tree[Int]`

defined like this:

```
val n = Node(1, Leaf(2), Node(3, Leaf(5), Node(4, Leaf(42), Leaf(50))))
```

The tree has a structure that looks like this:

We want to get the right most value, which is 50. In order to do that with the current implementation of `foldTree`

, we need to provide it two methods:

`f1: A => B`

: Given an`A`

, project a`B`

value`f2: (A, B, B) => B`

: Given one`A`

and two`B`

values, project a`B`

.

We can see that `f1`

is applied over a `Leaf`

, and `f2`

is applied over a `Node`

(hence the different number of elements provided to each method). So this gives us a hint that the functions we provide to `foldTree`

will be applied to each one, respectively.

Packed with that knowledge, given our tree:

```
val n = Node(1, Leaf(2), Node(3, Leaf(55), Node(4, Leaf(42), Leaf(50))))
```

We provide the following method:

```
println(foldTree[Int, Int](identity)((x, y, z) => z)(n))
```

What this means is as follows:

- If we encounter a
`Leaf`

node and map over it (by applying`f1`

on it), we simply want to extract it’s value. - When encountering a
`Node`

element (and applying`f2`

to it), we want to take the*right most element*, which is projected by the third element`z`

in our method.

Running this, yields the expected result: `50`

.

If we want to expand this generically for any `A`

, we can say:

```
def extractRightmostValue[A](tree: Tree[A]) =
foldTree[A, A](identity)((x, y, z) => z)(tree)
```

### Answer 2:

```
fold_tree[A,A](identity)((_,_,z) => z)(t)
```

This should work because the method takes in type A and returns type A. It tells the method if we are at a leaf, just return the leafs value. If we have a node and a left tree and a right tree, return the right tree’s value.

## References

- Database Administration Tutorials
- Programming Tutorials & IT News
- Linux & DevOps World
- Ebook Reviews
- eSport Matches, Skills Tutorials & News
- Entertainment & General News
- Check your public IP Address precisely