MaxPath

MaxPathGraph.kt

import java.lang.IllegalStateException

fun main() {
    node(5) {
        left(3) {
            left(2) {
                left(3)
                right(6)
            }
        }
        right(-14) {
            left(3)
            right(2) {
                left(3)
                right(10)
            }
        }
    }.maxPath().let(::println)
}

data class Node(val left: Node?, val right: Node?, val value: Int) {
    fun maxPath(): Int = provideInfo().mostOptimalSubtree

    private fun provideInfo(): PathInfo {
        val leftInfo = left?.provideInfo()
        val rightInfo = right?.provideInfo()
        val mostOptimalPath = listOfNotNull(
            leftInfo?.let { it.mostOptimalPath + value },
            rightInfo?.let { it.mostOptimalPath + value },
            value
        ).max() ?: throw IllegalStateException()
        val mostOptimalSubtree = listOfNotNull(
            leftInfo?.mostOptimalSubtree,
            rightInfo?.mostOptimalSubtree,
            leftInfo?.let { it.mostOptimalPath + value },
            rightInfo?.let { it.mostOptimalPath + value },
            value,
            if (leftInfo != null && rightInfo != null) (value + leftInfo.mostOptimalPath + rightInfo.mostOptimalPath) else null
        ).max() ?: throw IllegalStateException()
        return PathInfo(mostOptimalSubtree, mostOptimalPath)
    }

    private data class PathInfo(val mostOptimalSubtree: Int, val mostOptimalPath: Int)
}

fun node(value: Int, action: NodeBuilder.() -> Unit): Node = NodeBuilder(value).apply(action).build()

class NodeBuilder(private val value: Int) {
    private var left: NodeBuilder? = null
    private var right: NodeBuilder? = null
    fun build(): Node = Node(left?.build(), right?.build(), value)

    fun left(value: Int, action: NodeBuilder.() -> Unit = {}) {
        left = NodeBuilder(value).apply(action)
    }

    fun right(value: Int, action: NodeBuilder.() -> Unit = {}) {
        right = NodeBuilder(value).apply(action)
    }
}