August 27, 2024
P62 - Collect nodes at a given level in a list.
A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a method valuesAtLevel to collect all node values at a given level into a list.
> Node('a', Node('b'), Node('c', Node('d'), Node('e'))).valuesAtLevel(2)
[b, c]Using valuesAtLevel it is easy to construct a method to create the level-order sequence of the nodes. However, there are more efficient ways to do that.
kotlin
package org.kotlin99.binarytrees
import com.natpryce.hamkrest.assertion.assertThat
import org.junit.Test
import org.kotlin99.binarytrees.Tree.End
import org.kotlin99.binarytrees.Tree.Node
import org.kotlin99.common.containsAll
fun <T> Tree<T>.valuesAtLevel(n: Int): List<T> =
when (this) {
End -> emptyList()
is Node<T> ->
if (n == 1) listOf(this.value)
else left.valuesAtLevel(n - 1) + right.valuesAtLevel(n - 1)
}
class P62Test {
@Test fun `collect node values at particular level`() {
val tree = Node("a", Node("b"), Node("c", Node("d"), Node("e")))
assertThat(tree.valuesAtLevel(0), containsAll(emptyList()))
assertThat(tree.valuesAtLevel(1), containsAll("a"))
assertThat(tree.valuesAtLevel(2), containsAll("b", "c"))
assertThat(tree.valuesAtLevel(3), containsAll("d", "e"))
assertThat(tree.valuesAtLevel(4), containsAll(emptyList()))
}
}
Be first to comment