Kotlin: Find leaf nodes paths in N-ary tree

Gordon Passy — Tue, 26 Oct 2021 19:58:04 +0000

Definitions

A tree is a data structure where a node can have zero or more children. Each node contains a value and the top-most node is called the root. A node without children is called a leaf node.

The N-ary tree is a tree that allows you to have n(n ≥ 0)number of children of a particular node as opposed to binary trees that that allow you to have at most 2 children of a particular node.

Here's a sample N-ary tree we'll use to get paths to leaf nodes.

In the above tree, 1 is the root node, 2, 3 and 4 are children of the root node. Nodes 5,6,7,8,9,10,11 are all leaf nodes because they have no children.

Task

Given the above N-ary tree, write a solution to get paths to the leaf nodes. The solution should return list of paths to the leaf nodes as shown below:

    [1,2,5]
    [1,2,6]
    [1,2,7]
    [1,3,8]
    [1,4,9]
    [1,4,10]
    [1,4,11]

Solution

First, we define the N-ary tree data class.

data class Node<T>(var value: T) {
    var parent: Node<T>? = null
    var children: MutableList<Node<T>> = mutableListOf()

     fun addChild(node: Node<T>) {
         children.add(node)
         node.parent = this
     }
    fun hasChildren(): Boolean =
        children.size >= 1
}

Next we create a function makeTree() that constructs the above n-ary tree.

fun makeTree(): Node<Int> {
    val root =  Node(1)
    val node2 = Node(2)
    root.addChild(node2)
    val node3 = Node(3)
    root.addChild(node3)
    val node4 = Node(4)
    root.addChild(node4)
    val node5 = Node(5)
    node2.addChild(node5)
    val node6 = Node(6)
    node2.addChild(node6)
    val node7 = Node(7)
    node2.addChild(node7)
    val node8 = Node(8);
    node3.addChild(node8)
    val node9 = Node(9)
    node4.addChild(node9)
    val node10 = Node(10)
    node4.addChild(node10)
    val node11 = Node(11)
    node4.addChild(node11)
    return root
}

To get the paths to the leaf nodes we will use Depth First Search. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

We will traverse the N-ary tree and keep inserting every node to the path until a leaf node is found. When a leaf node is found, we add the path to the result and remove the last added leaf node from the path and check for the next leaf node.

Here's the recursive backtracking routine:

private fun findLeafNodePaths(
    node: Node<Int>,
    result: MutableList<List<Int>>,
    path: MutableList<Int>): MutableList<List<Int>> {

    path.add(node.value)
    if (!node.hasChildren()) { // leaf node
        result.add(path.map { it }) // add path to the result
        path.removeLast()//
    } else {
        for (child in node.children) {
            findLeafNodePaths(child, result, path)
        }
        path.removeLast()
    }
    return result
}

Here's the main function to create the n-ary tree and print paths to the leaf nodes:

fun main() {
    findLeafNodePaths(makeTree(),  mutableListOf(), mutableListOf() ).forEach {
        println(it)
    }
}

Complete Code:

Kotlin data class to xml

Gordon Passy — Wed, 08 Jul 2020 08:47:17 +0000

Let’s say you have this sample data class that you want to serialize to xml

data class SampleDataClass(
        val externalTxnId: String,
        val merchantTxnId: String,
        val reference: String
)

Steps

If you’re using maven, add the jackson-dataformat-xml dependency on your pom.xml file

<dependency>
   <groupId>com.fasterxml.jackson.dataformat</groupId>
   <artifactId>jackson-dataformat-xml</artifactId>
   <version>2.10.1</version>
</dependency>

Initialize the XmlMapper

val xmlMapper = XmlMapper(
        JacksonXmlModule().apply { setDefaultUseWrapper(false) }
).apply {
        enable(SerializationFeature.INDENT_OUTPUT)
}

Initialize your data class and use the mapper’s writeValueAsString() method to get the xml value.

fun main() {
        val xmlMapper = XmlMapper(
                JacksonXmlModule().apply { setDefaultUseWrapper(false) }
        ).apply {
                enable(SerializationFeature.INDENT_OUTPUT)
                enable(SerializationFeature.WRAP_ROOT_VALUE)
        }

        val data = SampleDataClass(
                externalTxnId = "07026984141550752666",
                merchantTxnId = "07026984141550752666",
                reference     = "MERCHPAY"
        )
        val xml = xmlMapper.writeValueAsString(data)
        println(xml)
}

//This will give out the following output

<SampleDataClass>
  <externalTxnId>07026984141550752666</externalTxnId>
  <merchantTxnId>07026984141550752666</merchantTxnId>
  <reference>MERCHPAY</reference>
</SampleDataClass>

Default root element used is the simple name of the data class. So if you don’t want to use the defaults, that’s where the annotation @JacksonXmlRootElement for root element and @JacksonXmlProperty for fields come in.

Let’s say we want the root element to be labelled COMMAND and the fields externalTxnId to EXTTRID, merchantTxnId to MERCHANT_TXN_ID and finally reference to REFERENCE. To have this implemented we’ll add the annotations to the data class as below: