concept tree in category kotlin

This is an excerpt from Manning's book The Joy of Kotlin. Login to get full access to this book.

Graphs are collections in which each element is related to multiple other elements. A particular example is the tree and, more specifically, the binary tree, where each element is related to two other elements. You’ll learn more about trees in chapter 10.

The tree represented in the figure isn’t common because its elements are of different types. It’s a tree of Any. Most often, you’ll deal with trees of a more specific type, such as trees of integers.

In figure 10.1, you can see that a tree is a recursive structure. Each branch leads to a new tree (often called a subtree). You can also see that some branches lead to a single element. This isn’t a problem because this single element is, in fact, a tree with empty branches. Such terminal elements are often called leaves. Also note the T element: it has a left branch but no right one. This is because the right branch is empty and is not represented. From this, you can infer the definition of a binary tree. A tree is one of the following:

Binary trees can be more or less balanced. A perfectly balanced tree is a tree in which the two branches of all subtrees contain the same number of elements. Figure 10.2 shows three examples of trees with the same elements. The first tree is perfectly balanced and the last tree is totally unbalanced. Perfectly balanced binary trees are sometimes called perfect trees.

Figure 10.2 Trees can be more or less balanced. The top tree is perfectly balanced because the two branches of all subtrees contain the same number of elements. The tree on the right is a singly linked list, which is a special case of a totally unbalanced tree.

In this figure, the tree on the right is, in fact, a singly linked list. A singly linked list can be seen as a special case of a totally unbalanced tree.

Listing 10.1 The minimal Tree implementation

sealed class Tree<out A: Comparable<@UnsafeVariance A>> {    #1    #2  

    abstract fun isEmpty(): Boolean

    internal object Empty : Tree<Nothing>() {    #3  

        override fun isEmpty(): Boolean = true

        override fun toString(): String = "E"    #4  
    }

    internal class T<out A: Comparable<@UnsafeVariance A>>(
                           internal val left: Tree<A>,    #5    #6  
                           internal val value: A,
                           internal val right: Tree<A>) : Tree<A>() {

        override fun isEmpty(): Boolean = false

        override fun toString(): String =
                    "(T $left $value $right)"    #4  
    }

    companion object {

        operator fun <A: Comparable<A>> invoke(): Tree<A> =
                                        Empty    #8  
    }
}

#1   The Tree class is parameterized, and the parameter type must extend Comparable.
#2   The Tree class is covariant on A, but the Comparable interface is contravariant, so you must deal with that.
#3   The empty tree is represented by a singleton object parameterized with Nothing.
#4   The toString functions are minimal implementations to help see the content of a tree.
#5   The T subclass represents a non-empty tree.
#6   All properties are internal so that they can’t be accessed directly from other modules.
#8   The invoke function returns the Empty singleton.