How to deep copy an N-Ary tree in kotlin

Question

If you want to create a deep copy of a tree (so that each node in the tree is deep-copied), you have to use a recursive algorithm provided in the answer below.

I have not found such an article on SO, regarding realization of this in Kotlin, let alone the articles on N-Ary trees were too few and sparse. That is why I am leaving the code here for anyone who needs to solve such a problem.

Answer 1

Suppose, we have a tree class with type T:

data class Tree<T>(var root: TreeNode<T>) {
}

In that class we have a TreeNode class:

data class TreeNode<T>(var name: String, private var nodeAttributes: MutableList<T> = mutableListOf()) {

    var parent: TreeNode<T>? = null
    val childrenList: MutableList<TreeNode<T>> = mutableListOf()
    var depth = 0
        private set
    var index = 0
        private set
    var childLowestIndex = 0
        private set

    fun addChild(node: TreeNode<T>) {
        node.parent = this
        node.index = this.childLowestIndex
        this.childLowestIndex++
        node.depth = this.depth + 1
        childrenList.add(node)
    }
}

A TreeNode has a String name and nodeAttributes — the latter being a Mutable list of the type T that you Tree was initialized with. It allows to assign and retrieve an arbitrary-length list of data of a chosen type to/from any TreeNode, upon creation or later via addAttributes() and getAttributes()

The tree structure is built upon nested TreeNodes.

Suppose we have to deep copy this Tree or a specific TreeNode. In order to do that, to the Tree class we should add such a method

fun clone() = Tree(this.root.clone())

But in order to deep copy the tree that is initialized with a root node, that holds the whole data structure, we have to also deep copy the whole data structure i.e. every TreeNode in the structure.

To do that we can add this method below to the TreeNode class:

    /**
     * Return a new independent instance of this TreeNode (deep copy), uses recursion
     */
    fun clone(): TreeNode<T> {
        val newNode = TreeNode(this.name, this.nodeAttributes.map { it }.toMutableList())
        newNode.depth = this.depth
        this.childrenList.forEach {
            val newChild = it.clone()
            newNode.addChild(newChild)
        }
        return newNode
    }

What this method does on each call is:

1. Creates a new temporary node newNode from the same initial parameters the node that clone() was called upon had

2. Copies depth of the node as well. No need to copy the rest of the parameters.

3. For each child of this node a clone() of that child is added as a child to this node, thus the function is recursive.

4. It goes until clone() on the deepest node is called, which has no children, thus no cloning is executed afterwards and clone() returns a deep copy of the deepest node.

5. The algorithm goes all the way back returning all new deep-copied nodes with their deep-copied children and adding them as children to the nodes higher in hierarchy, until the original node that clone() was called upon is reached

Thus, treeNode.clone() returns a deep copy of any selected treeNode.

And afterwards the deep copy of an original tree is created from the deep-copied original node. Once again:

fun clone() = Tree(this.root.clone())

I hope, this article was useful, feel free to add any corrections and suggestions in the comments.

Here is the link to the full code. https://github.com/lifestreamy/TreeBuilder/blob/master/src/main/kotlin/treeBuilder/Tree.kt