Kotlin: Find leaf nodes paths in N-ary tree

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:

	fun main() {
	findLeafNodePaths(makeTree(), mutableListOf(), mutableListOf() ).forEach {
	println(it)
	}
	}
	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
	}
	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 leaf node to the result
	path.removeLast()
	} else {
	for (child in node.children) {
	findLeafNodePaths(child, result, path)
	}
	path.removeLast()
	}
	return result
	}
	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
	}

view raw n-ary.kt hosted with ❤ by GitHub