I am trying to understand how I can rebuild a tree...

# getting-started

[james]

I am trying to understand how I can rebuild a tree from a flat list which is given to me by an API.
My model is simple: data class Reply(id: Int, parentId: Int, replies: List<Reply>) ... and I'm attempting to:

{
    "replies": [
        { id: 1, parent: 0 }  <- turn this     1
        { id: 2, parent: 1 }     into this ->  └── 2
        { id: 3, parent: 2 }                       ├── 3
        { id: 4, parent: 3 }                       │   └── 4
        { id: 5, parent: 2 }                       ├── 5
        { id: 6, parent: 2 }                       ├── 6
        { id: 7, parent: 2 }                       └── 7
    ]
}

does anyone have any experience in "unflattening" a list into a tree like this? I start out by using associateBy on my flat list and turn it into a mutable map, at which point I iterate the flat list itself and append the current item to any value in the map whose id matches the current iterator item's parentId. doing this I end up with a list where the first and second levels are correct, but third and deeper are empty

I've spent about 10 hours on this over the past 3 days and I've really gotten nowhere, just going in circles really. would love some guidance from anyone who has done this kind of thing with Kotlin

[Joffrey]

The idea of the map is good, because you need to access any node in your tree by id. Then you can define the node of trees with a mutable list of children so you can append to it. Also I'd suggest using null instead of 0 to signify "no parent".
Can there be multiple roots (parent=0) in your input?

[Joffrey]

One way to do it considering multiple top-level replies:

// the input type with just id and parent
data class RawReply(val id: Int, val parent: Int)

// the target type, representing nodes of the tree
data class Reply(val id: Int, val parent: Int, val replies: List<Reply>)

// an intermediate private type, to enable building the tree
private class ReplyBuilder(
    val id: Int,
    val parent: Int,
    val children: MutableList<ReplyBuilder> = mutableListOf()
) {
    fun build(): Reply = Reply(
        id = id,
        parent = parent,
        replies = children.map { it.build() },
    )
}

fun List<RawReply>.toReplyTree(): List<Reply> {
    val repliesById = associate { it.id to ReplyBuilder(it.id, it.parent) }

    val roots = mutableListOf<ReplyBuilder>()

    repliesById.values.forEach {
        if (it.parent == 0) { // consider using null for "no parent", it's clearer
            roots.add(it)
        } else {
            val parent = repliesById[it.parent] ?: error("Unknown parent reply ${it.parent}")
            parent.children.add(it)
        }
    }
    return roots.map { it.build() }
}

[Roukanken]

ye basically this ^
Idea is simple, you create a map of id -> mutable list of children
and then for each entry in replies you add it to correct place (you know it's parent id, so you know in which list of children it belongs)

and then you clean it up so you have nice data class

[Michael de Kaste]

I'd do it the following way:

declare an val-only interface with the values you've shown before:

interface Reply {
    val id: Int
    val parentId: Int?
    val replies: List<Reply>
}

then in the API you get the following data class:

data class ReplyImpl(
    override val id: Int,
    override val parentId: Int?,
    override val replies: MutableList<ReplyImpl> = mutableListOf()
) : Reply

now lets say you have the following list of ReplyImpls:

val replies = listOf(
        ReplyImpl(1, null),
        ReplyImpl(2, 1),
        ReplyImpl(3, 2),
        ReplyImpl(4, 3),
        ReplyImpl(5, 2),
        ReplyImpl(6, 2),
        ReplyImpl(7, 2)
    )

we can now associate them by their ID to provide a lookup table and loop through all the replies and add yourself to the parent list like so:

val repliesMap = replies.associateBy { it.id }
    var root: Reply? = null
    for (reply in replies) {
        if (reply.parentId != null) {
            repliesMap[reply.parentId]!!.replies.add(reply)
        } else {
            root = reply
        }
    }

printing the root afterwards gives (after some tidying)

ReplyImpl(id=1, parentId=null, replies=[
	ReplyImpl(id=2, parentId=1, replies=[
		ReplyImpl(id=3, parentId=2, replies=[
			ReplyImpl(id=4, parentId=3, replies=[])
		]), 
		ReplyImpl(id=5, parentId=2, replies=[]), 
		ReplyImpl(id=6, parentId=2, replies=[]), 
		ReplyImpl(id=7, parentId=2, replies=[])
	])
])

[Michael de Kaste]

you can also not declare an interface at all, but then you'd be communicating away a reply that's mutable.

[ephemient]

you could also build the reverse mapping, which will make everything easy (as long as there are no cycles)

val childrenByParentId = input.groupBy { it.parent }
fun getById(id: Int): Reply {
    val children = childrenByParentId[id]
        ?.map { getById(it.id) }
        .orEmpty()
    return Reply(id, children)
}
val root = input.singleOrNull { it.parent = 0 }
    ?.let { getById(it.id) }

[Joffrey]

Yep, that works if you don't need to remember the parent in the Reply type

[james]

you are all brilliant, thank you!

an intermediate class was the key to it.. I just went back and tested some of the methods I had built previously and realised 2 of them worked with using a builder pattern, like Joffrey suggested.

thank you all again. I don't feel quite so stupid now that I realise how close my solutions were, but I'm not sure how many days or weeks I would have continued going around in circles without your assistance 🙏

[Michael de Kaste]

Never feel stupid for learning!

[ephemient]

if you need the parent ID, or even the whole original reply object, that wouldn't be hard to set up with the reverse mapping. the only thing that it really doesn't handle is cycles, for which you need some mutability to build up piece-wise