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

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?

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

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=[])
	])
])

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) }

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

Reply

type

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 🙏

Never feel stupid for learning!

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