August 27, 2024
P71 - Determine the internal path length of a tree.
We define the internal path length of a multiway tree as the total sum of the path lengths from the root to all nodes of the tree. By this definition, the tree in the figure of problem P70B has an internal path length of 9. Write a method internalPathLength to return that sum.
> "afg^^c^bd^e^^^".convertToMTree().internalPathLength()
9kotlin
package org.kotlin99.multiwaytrees
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
fun MTree<*>.internalPathLength(): Int =
children.sumOf { it.nodeCount() + it.internalPathLength() }
class P71Test {
@Test fun `internal path of tree`() {
assertThat(MTree('a').internalPathLength(), equalTo(0))
assertThat(MTree('a', MTree('b'), MTree('c')).internalPathLength(), equalTo(2))
assertThat(MTree('a', MTree('b'), MTree('c', MTree('d'))).internalPathLength(), equalTo(4))
assertThat("afg^^c^bd^e^^^".convertToMTree().internalPathLength(), equalTo(9))
}
}
Be first to comment