August 27, 2024
P54 - Omitted; our tree representation will only allow well-formed trees.
A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves.
We will use the following classes to represent binary trees (see Tree.kt). An End is equivalent to an empty tree. A Node has a value, and two child trees. The toString() functions are relatively arbitrary and were written to produce minimal readable output.
Note the usage of variance annotation out T which makes classes covariant; it will be able to hold subtypes of whatever type it's created for.
End is declared as value because data classes must have at least one constructor parameter. End has type parameter of Nothing which is a subtype of every other type.
interface Tree<out T>
data class Node<out T>(val value: T, val left: Tree<T> = End, val right: Tree<T> = End) : Tree<T> {
override fun toString(): String {
val children = if (left == End && right == End) "" else " $left $right"
return "T($value$children)"
}
}
val End = object : Tree<Nothing>{
override fun toString() = "."
}The example of tree above can be written as:
Node('a',
Node('b',
Node('d'),
Node('e')),
Node('c', End,
Node('f', Node('g'),
End)))A tree with only a root node would be Node('a') and an empty tree would be End.
Score one for static typing.