Kotlin coding test course, finding the lowest common ancestor

Hello! In this session, we will solve the problem of finding the Lowest Common Ancestor (LCA) using Kotlin through a series of algorithmic problems. This problem is one of the important concepts dealing with tree structures and appears in various coding tests. This course will detail the problem definition, solution process, and optimization methods along with explanations of the topic.

Problem Definition

The problem is to find the lowest common ancestor of node A and node B when a tree structure is given. The Lowest Common Ancestor is the deepest ancestor among the ancestors of nodes A and B. For example, consider the tree structure shown below.

In this case, the lowest common ancestor of node 4 and node 5 is node 2. Additionally, the lowest common ancestor of node 4 and node 6 is node 1.

Input

First line: The number of nodes N in the tree (1 ≤ N ≤ 20,000)
From the second line to the N-1th line: Two integers a, b are given, indicating that a is the parent of b.
Last line: Two integers X, Y (1 ≤ X, Y ≤ N) which are the nodes for which we need to find the LCA.

Output

Print the node number of the lowest common ancestor.

Example Input

Example Output

Problem Solving Process

Now, I will explain the approach to solving the problem. In tree structures, it is common to use DFS (Depth-First Search) or BFS (Breadth-First Search) to store the depth of nodes and record parent nodes. This method allows us to compare the depth of each node and find the common ancestor.

1. Build the Tree

First, we need to build the tree based on the information given in the input. In Kotlin, this can be implemented using a list to store the children of each node.


data class TreeNode(val id: Int) {
    val children = mutableListOf()
}

fun buildTree(n: Int, edges: List>): Map {
    val nodes = mutableMapOf()
    edges.forEach { (parentId, childId) ->
        val parentNode = nodes.getOrPut(parentId) { TreeNode(parentId) }
        val childNode = nodes.getOrPut(childId) { TreeNode(childId) }
        parentNode.children.add(childNode)
    }
    return nodes
}

2. Store Depth and Parent Nodes

We will write a function to store depth and parent nodes using DFS. This will be helpful for finding the LCA later on.


val depth = mutableMapOf()
val parent = mutableMapOf()

fun dfs(node: TreeNode, dep: Int) {
    depth[node.id] = dep
    for (child in node.children) {
        parent[child.id] = node.id
        dfs(child, dep + 1)
    }
}

// Example usage
val root = nodes[1] // Root node (ID: 1)
dfs(root, 0)

3. Find LCA

Now we will implement a function to find the LCA of the two nodes. We will compare the two given nodes to adjust their depths and find the ancestor.


fun findLCA(x: Int, y: Int): Int {
    // Adjust depth
    var a = x
    var b = y
    while (depth[a] > depth[b]) {
        a = parent[a]!!
    }
    while (depth[b] > depth[a]) {
        b = parent[b]!!
    }
    while (a != b) {
        a = parent[a]!!
        b = parent[b]!!
    }
    return a
}

// Example usage
val lca = findLCA(4, 6)
println("LCA: $lca")

4. Full Implementation

Now, we will consolidate all the steps to write the complete program.


fun main() {
    val n = readLine()!!.toInt()
    val edges = mutableListOf>()
    repeat(n - 1) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        edges.add(Pair(a, b))
    }
    val (x, y) = readLine()!!.split(" ").map { it.toInt() }

    val nodes = buildTree(n, edges)

    val depth = mutableMapOf()
    val parent = mutableMapOf()

    fun dfs(node: TreeNode, dep: Int) {
        depth[node.id] = dep
        for (child in node.children) {
            parent[child.id] = node.id
            dfs(child, dep + 1)
        }
    }

    val root = nodes[1]
    dfs(root, 0)

    fun findLCA(x: Int, y: Int): Int {
        var a = x
        var b = y
        while (depth[a] > depth[b]) {
            a = parent[a]!!
        }
        while (depth[b] > depth[a]) {
            b = parent[b]!!
        }
        while (a != b) {
            a = parent[a]!!
            b = parent[b]!!
        }
        return a
    }

    val lca = findLCA(x, y)
    println("LCA: $lca")
}

Optimization

The current method calculates depth and parent nodes using DFS and then finds the LCA. This method operates in O(N) time, and finding the LCA takes O(log N) time complexity. However, for larger values of N, it is possible to utilize optimized algorithms such as “Sparse Table” or “Binary Lifting.” These methods can further reduce time complexity.

Conclusion

In this lecture, we learned about how to find the lowest common ancestor. The LCA problem in tree structures is a common topic in algorithm problems, so it is important to practice thoroughly until it becomes second nature. Try writing and understanding the code step by step. Next time, we will return with another topic. Thank you!