sealed class Tree {

    abstract fun size(): Int
    abstract fun playtime(): Int

    fun addSorted(valueSong: Song, comp: Comparator<Song>): Tree = when (this) {
        is EmptyTree -> DataNode(valueSong)
        is DataNode -> if (0 <= comp.compare(valueSong, this.songValue))
            DataNode(songValue, left.addSorted(valueSong, comp), right)
        else
            DataNode(songValue, left, right.addSorted(valueSong, comp))
    }

    fun forEachSong(f: (v: Song) -> Unit) {
        when (this) {
            is EmptyTree -> {}
            is DataNode -> f(this.songValue)
        }
    }

    abstract fun processPreOrder(f: (v: Song) -> Unit)
    abstract fun processPostOrder(f: (v: Song) -> Unit)
    abstract fun processInOrder(f: (v: Song) -> Unit)
}

object EmptyTree : Tree() {

    override fun size(): Int = 0

    override fun playtime(): Int = 0

    override fun processPreOrder(f: (v: Song) -> Unit) {}
    override fun processPostOrder(f: (v: Song) -> Unit) {}
    override fun processInOrder(f: (v: Song) -> Unit) {}
}

class DataNode(val songValue: Song, val left: Tree = EmptyTree, val right: Tree = EmptyTree) : Tree() {

    override fun size(): Int = left.size() + 1 + right.size()

    override fun playtime(): Int = left.playtime() + this.songValue.spieldauer + right.playtime()

    override fun processPreOrder(f: (v: Song) -> Unit) {
        forEachSong(f) // Diesen Knoten zuerst verarbeiten
        left.processPreOrder(f) // dann den gesamten linken und
        right.processPreOrder(f) // rechten Teilbaum verarbeiten
    }

    override fun processPostOrder(f: (v: Song) -> Unit) {
        left.processPostOrder(f) // Erst den linken, dann den
        right.processPostOrder(f) // rechten Teilbaum vollständig verarbeiten
        forEachSong(f) // am Ende den Knoten selbst verarbeiten
    }

    override fun processInOrder(f: (v: Song) -> Unit) {
        left.processInOrder(f) // erst den linken Teilbaum verarbeiten
        forEachSong(f) // diesen Knoten verarbeiten
        right.processInOrder(f) // rechten Teilbaum verarbbeiten
    }
}

class SongTreeContainer(val songliste: MutableList<Song>, comp: Comparator<Song>) {

    var songTreeRoot: Tree = EmptyTree

    init {
        for (x in songliste) {
            songTreeRoot = songTreeRoot.addSorted(x, comp)
        }
    }

    fun size() = songTreeRoot.size()

    fun playtime() = songTreeRoot.playtime()

    fun addSorted(valueSong: Song, comp: Comparator<Song>){
        songTreeRoot = songTreeRoot.addSorted(valueSong, comp)
    }

    fun forEachSong(f: (v: Song) -> Unit) = songTreeRoot.processInOrder(f)
}