kotlin coding test course, finding the diameter of a tree

Hello. Today we will learn how to find the diameter of a tree using Kotlin.
In this tutorial, we will explain the basic concepts of trees, the definition of diameter, and the algorithmic approach in detail,
and we will practice through example code.

Tree and Tree Diameter

A tree is a non-linear data structure in which each node can have zero or more children.
A tree has the following characteristics:

A tree has a root node, and the root is connected to other nodes.
A child node must have exactly one parent node.
The path from the root to a leaf node defines the height of the tree.

The diameter of a tree refers to the length of the longest path within the tree.
The diameter can always be defined as the distance between two leaf nodes.
For example, consider the tree below:

The diameter of this tree is the longest path from node 4 to node 5, which is 4-2-5.
Therefore, the length of the diameter is 2.

Algorithm for Finding the Diameter of a Tree

To find the diameter, you can use DFS (Depth-First Search) or BFS (Breadth-First Search).
Generally, DFS is the more commonly used method.
The basic idea of the algorithm is as follows:

Select an arbitrary node (root node) and perform the first DFS. During this, find the farthest node.
Starting from the node found in the first DFS, perform a second DFS.
Return the maximum distance (diameter) calculated in the second DFS.

Kotlin Code Implementation

Now, we will implement this algorithm in Kotlin.
We will use data classes to represent nodes and edges, and
we will create a DFS method to calculate the diameter of the tree.

Data Class and Graph Initialization

Kotlin
data class Edge(val to: Int, val weight: Int)

class Tree(val size: Int) {
    private val graph = Array(size) { mutableListOf() }

    fun addEdge(from: Int, to: Int, weight: Int) {
        graph[from].add(Edge(to, weight))
        graph[to].add(Edge(from, weight))
    }

    fun diameter(start: Int): Int {
        // Perform the first DFS
        val (farthestNode, _) = dfs(start, BooleanArray(size), 0)
        // Perform the second DFS
        val (_, diameter) = dfs(farthestNode, BooleanArray(size), 0)
        return diameter
    }

    private fun dfs(node: Int, visited: BooleanArray, distance: Int): Pair {
        visited[node] = true
        var maxDistance = distance
        var farthestNode = node

        for (edge in graph[node]) {
            if (!visited[edge.to]) {
                val (newFarthestNode, newDistance) = dfs(edge.to, visited, distance + edge.weight)
                if (newDistance > maxDistance) {
                    maxDistance = newDistance
                    farthestNode = newFarthestNode
                }
            }
        }

        return Pair(farthestNode, maxDistance)
    }
}

Code Explanation

– Edge data class: A class that defines an edge.
It includes the node and weight.

– Tree: A class that represents a tree. It initializes the size of the tree and the graph data structure.
Edges can be added using the addEdge method.

– diameter method: A method that calculates the diameter.
It performs the first and second DFS.

– dfs method: A recursive method that performs depth-first search.
It checks the visited nodes and calculates the maximum distance.
It returns the farthest node and the distance based on the maximum distance.

Test Cases

To test the diameter of the tree, we will add edges as shown below and print the results.

Kotlin
fun main() {
    val tree = Tree(5)
    tree.addEdge(0, 1, 1)
    tree.addEdge(0, 2, 2)
    tree.addEdge(1, 3, 1)
    tree.addEdge(1, 4, 1)

    val diameter = tree.diameter(0)
    println("The diameter of the tree is: $diameter")
}

Execution Result

    The diameter of the tree is: 4

Conclusion

In this tutorial, we explored how to find the diameter of a tree using Kotlin.
This approach using DFS is useful for dealing with tree data structures and can be applied in various applications.
I hope this tutorial helps in solving tree-related problems.

We plan to cover various algorithms and coding test problems in the future, so please look forward to it!
Thank you.