Building double-linked tree structures


Would like some advice for what is the most Kotlin idiomatic way to build a double-linked tree structure. Each node in the tree can have zero or more children, and every node other than the root has exactly one parent. After it has been constructed the tree is immutable. I need to be able to traverse the tree from bottom up as well as top down.

At present I’m building the tree bottom up, then doing a post build pass through the tree filling in each node’s parent. So each node contains properties:-

private val children : List<Node>
private var parent : Node?

Which works fine, but I don’t much like the way I have parent exposed as var when it is immutable after the post-build stage, as this blocks kotlin’s null smart casts. I can’t make parent lateinit as I need the null value for the tree root.

I could alternatively build the tree top down, passing the parent as an argument to child constructor, and having the child call back to add itself.

private val children : MutableList<Node>
private val parent : Node?

This avoids the second pass, makes everything val and allows null smart casts. But to me that feels worse as it implies the number of children at a node is mutable.

What do people consider is the more idiomatic?

submitted by /u/Falcon731
[link] [comments]