Functional Programming in Kotlin, Manning book - binary tree structure

Question

I've been working through the exercises in this book. It's well-written, but moves very fast. So far, I'm keeping up.

But, having zero experience with binary trees I'm stuck on this one. Here's the assignment:

Write a function size that counts the number of nodes (leaves and branches) in a tree.

And here's the tree structure as a sealed class:

sealed class Tree<out A>
data class Leaf<A>(var value: A) : Tree<A>()
data class Branch<A>(val left: Tree<A>, val right: Tree<A>) : Tree<A>()

I had to search for info on binary trees, and found a sample in Kotlin that I could understand.

But that sample had a tri-state structure, whereas, the exercise has dual-state:

class BinaryNode<Element>(
    val value: Element,
    var leftChild: BinaryNode<Element>? = null,
    var rightChild: BinaryNode<Element>? = null
) {

So, I'm having trouble constructing a valid binary tree using the sealed class, that I can test the exercise solution on, which is:

fun <A> size(tree: Tree<A>): Int =
    when (tree) {
        is Leaf -> 1
        is Branch -> 1 + size(tree.left) + size(tree.right)
    }

Solution seems reasonable looking at it, but can't quite figure out tree construction.

Any help would be appreciated.

Adam Millerchip Adam Millerchip · Accepted Answer · 2021-08-02T00:19:15

Here's a simple example:

fun main() {
    val tree = Branch(
        Branch(
            Leaf(1),
            Leaf(2)
        ),
        Branch(
            Leaf(3),
            Branch(
                Leaf(4),
                Leaf(5)
            )
        )
    )
    println(size(tree))
}

This prints 9, which is the 5 leaves plus the branches.

Functional Programming in Kotlin, Manning book - binary tree structure

1 Answers