test.kt

import java.util.LinkedList
import java.util.Deque
import java.util.ArrayList

data class TreeNode<T>(val value : T, val children : List<TreeNode<T>> = listOf())

public fun <T, Acc> treeFoldBFS(root : TreeNode<T>, initialValue : Acc, foldFunction : (Acc, T) -> Acc) : Acc =
        treeFoldImpl(root, LinkedList(), {q -> q.removeLast()}, initialValue, foldFunction)

public fun <T, Acc> treeFoldDFS(root : TreeNode<T>, initialValue : Acc, foldFunction : (Acc, T) -> Acc) : Acc =
        treeFoldImpl(root, LinkedList(), {q -> q.removeFirst()}, initialValue, foldFunction)

fun <T, Acc> treeFoldImpl(root : TreeNode<T>, deq : Deque<TreeNode<T>>, pop : (Deque<TreeNode<T>>) -> TreeNode<T>, initialValue : Acc, foldFunction : (Acc, T) -> Acc) : Acc {
    var acc = initialValue
    deq.addFirst(root)
    
    while (deq.notEmpty) {
        val node = pop(deq)
        acc = foldFunction(acc, node.value)
        node.children.forEach { deq.addFirst(it) }
    }
    
    return acc
}

fun <Acc : MutableCollection<T>, T> collectorFoldFunction(acc : Acc, e : T) : Acc {
    acc.add(e)
    return acc
}

// ================= test

fun makeExampleTree() : TreeNode<String> {
    val h = TreeNode("h")
    val d = TreeNode("d")
    val e = TreeNode("e", listOf(h))
    val f = TreeNode("f")
    val g = TreeNode("g")

    val b = TreeNode("b", listOf(d, e))
    val c = TreeNode("c", listOf(f, g))

    return TreeNode("a", listOf(b, c))
}

fun main(args : Array<String>) {
  val r = treeFoldBFS(makeExampleTree(), ArrayList<String>(), ::collectorFoldFunction)
  println(r)
}