Kotlin Coding Test Course: Finding the Parent of a Tree

Hello! Today we will learn about one of the data structures that often appears in coding tests: trees. In particular, we will address the problem of finding the parent of a specific node in a tree. Trees are used as fundamental data structures in various problems, and due to their characteristics, they require different algorithms and problem-solving methods.

Problem Description

Write a program that finds and returns the parent node of a specific node in the given tree. The tree is not empty, and each node is represented by an integer as a unique ID.

Input:

• Number of nodes in the tree N (1 ≤ N ≤ 100,000)
• Parent node information (an array P consisting of N-1 integers)
• The node X for which the parent needs to be found (1 ≤ X ≤ N)

Output:

Print the ID of the parent node of node X.

Example

Input:

    5
    1 1 2 2
    3
    

Output:

    1
    

Here, the parent node of node 3 is 1.

Problem Solving Process

To solve this problem, it is important to understand the tree structure and use the array that declares the parents. To understand the tree, let’s first look at its characteristics.

Characteristics of Trees

• A tree has a hierarchical structure, where each node can have only one parent.
• The root node has no parent.
• When there are N nodes, the parent information can be easily represented in an array.
• It is important to store information in a way that makes it easy to understand the relationship between parents and children.

Approach

1. We can access the parent of each node using the parent node information P.
2. Through the array P, we can easily find the parent of a child node using its index.
3. To find the parent node of the given node X, we return P[X-1].

Code Implementation

Now, let’s practice writing the code to solve the problem in Kotlin.

fun findParent(n: Int, parentInfo: IntArray, x: Int): Int {
    return parentInfo[x - 1]  // The parent of X is defined as P[X-1]
}

fun main() {
    val n = 5
    val parentInfo = intArrayOf(1, 1, 2, 2)  // Parent node information
    val x = 3  // The node to be searched
    println(findParent(n, parentInfo, x))  // Print the result
}
    

Time Complexity

This algorithm has a time complexity of O(1). The reason is that we simply access the index in the array to find the parent node. This approach allows for quick retrieval of the parent node even with a large number of nodes.

Test Cases

Let’s take a look at some additional test cases:

• Test Case 1:

        Input: 
        4
        1 1 2 
        1
        Output:
        -1 (The root node has no parent)
        

• Test Case 2:

        Input:
        10
        2 2 3 3 4 4 5 5
        6
        Output:
        4
        

Conclusion

In this post, we learned how to prepare for coding tests based on the problem of finding the parent of a tree. Since a basic understanding of tree structures is important, it is essential to study trees well before solving algorithm problems. I hope to enhance your algorithm skills through frequently used tree-related problems. In the next post, I will prepare another tree-related problem.

Thank you all for your hard work!