Kotlin: Find leaf nodes paths in N-ary tree
Tags: kotlin, recursion, backtracking, depthfirstsearch
Published: 2021-10-26 19:58:04

---
title: Kotlin: Find leaf nodes paths in N-ary tree
published: true
description: 
tags: Kotlin, Recursion, Backtracking, DepthFirstSearch
//cover_image: https://i.postimg.cc/nLJtWzMc/n-ary-tree.png
---

## 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](https://www.cct.lsu.edu/~sidhanti/tutorials/data_structures/page255.html) 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.
[![n-ary-tree.png](https://i.postimg.cc/nLJtWzMc/n-ary-tree.png)](https://postimg.cc/LJN7Ymzr)

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](https://iq.opengenus.org/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: 

{% gist https://gist.github.com/gordonpassy/5148f18f6ca001c44dcf3eb3beddcf0c %}