{"id":35174,"date":"2024-11-01T09:36:26","date_gmt":"2024-11-01T09:36:26","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35174"},"modified":"2024-11-01T11:44:46","modified_gmt":"2024-11-01T11:44:46","slug":"kotlin-coding-test-course-finding-the-parent-of-a-tree","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35174\/","title":{"rendered":"Kotlin Coding Test Course: Finding the Parent of a Tree"},"content":{"rendered":"<div class=\"post\">\n<p>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.<\/p>\n<h2>Problem Description<\/h2>\n<p>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.<\/p>\n<p><strong>Input:<\/strong><\/p>\n<ul>\n<li>Number of nodes in the tree N (1 \u2264 N \u2264 100,000)<\/li>\n<li>Parent node information (an array P consisting of N-1 integers)<\/li>\n<li>The node X for which the parent needs to be found (1 \u2264 X \u2264 N)<\/li>\n<\/ul>\n<p><strong>Output:<\/strong><\/p>\n<p>Print the ID of the parent node of node X.<\/p>\n<h2>Example<\/h2>\n<p><strong>Input:<\/strong><\/p>\n<pre>\n    5\n    1 1 2 2\n    3\n    <\/pre>\n<p><strong>Output:<\/strong><\/p>\n<pre>\n    1\n    <\/pre>\n<p>Here, the parent node of node 3 is 1.<\/p>\n<h2>Problem Solving Process<\/h2>\n<p>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&#8217;s first look at its characteristics.<\/p>\n<h3>Characteristics of Trees<\/h3>\n<ul>\n<li>A tree has a hierarchical structure, where each node can have only one parent.<\/li>\n<li>The root node has no parent.<\/li>\n<li>When there are N nodes, the parent information can be easily represented in an array.<\/li>\n<li>It is important to store information in a way that makes it easy to understand the relationship between parents and children.<\/li>\n<\/ul>\n<h3>Approach<\/h3>\n<ol>\n<li>We can access the parent of each node using the parent node information P.<\/li>\n<li>Through the array P, we can easily find the parent of a child node using its index.<\/li>\n<li>To find the parent node of the given node X, we return P[X-1].<\/li>\n<\/ol>\n<h3>Code Implementation<\/h3>\n<p>Now, let&#8217;s practice writing the code to solve the problem in Kotlin.<\/p>\n<pre><code>\nfun findParent(n: Int, parentInfo: IntArray, x: Int): Int {\n    return parentInfo[x - 1]  \/\/ The parent of X is defined as P[X-1]\n}\n\nfun main() {\n    val n = 5\n    val parentInfo = intArrayOf(1, 1, 2, 2)  \/\/ Parent node information\n    val x = 3  \/\/ The node to be searched\n    println(findParent(n, parentInfo, x))  \/\/ Print the result\n}\n    <\/code><\/pre>\n<h2>Time Complexity<\/h2>\n<p>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.<\/p>\n<h2>Test Cases<\/h2>\n<p>Let&#8217;s take a look at some additional test cases:<\/p>\n<ul>\n<li><strong>Test Case 1:<\/strong><\/li>\n<pre>\n        Input: \n        4\n        1 1 2 \n        1\n        Output:\n        -1 (The root node has no parent)\n        <\/pre>\n<li><strong>Test Case 2:<\/strong><\/li>\n<pre>\n        Input:\n        10\n        2 2 3 3 4 4 5 5\n        6\n        Output:\n        4\n        <\/pre>\n<\/ul>\n<h2>Conclusion<\/h2>\n<p>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.<\/p>\n<p>Thank you all for your hard work!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <a href=\"https:\/\/atmokpo.com\/w\/35174\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Kotlin Coding Test Course: Finding the Parent of a Tree&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[106],"tags":[],"class_list":["post-35174","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Kotlin Coding Test Course: Finding the Parent of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/35174\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Kotlin Coding Test Course: Finding the Parent of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"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 &hellip; \ub354 \ubcf4\uae30 &quot;Kotlin Coding Test Course: Finding the Parent of a Tree&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35174\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:36:26+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:44:46+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/35174\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35174\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Kotlin Coding Test Course: Finding the Parent of a Tree\",\"datePublished\":\"2024-11-01T09:36:26+00:00\",\"dateModified\":\"2024-11-01T11:44:46+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35174\/\"},\"wordCount\":444,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35174\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35174\/\",\"name\":\"Kotlin Coding Test Course: Finding the Parent of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:36:26+00:00\",\"dateModified\":\"2024-11-01T11:44:46+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35174\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35174\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35174\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Kotlin Coding Test Course: Finding the Parent of a Tree\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Kotlin Coding Test Course: Finding the Parent of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/35174\/","og_locale":"ko_KR","og_type":"article","og_title":"Kotlin Coding Test Course: Finding the Parent of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"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 &hellip; \ub354 \ubcf4\uae30 \"Kotlin Coding Test Course: Finding the Parent of a Tree\"","og_url":"https:\/\/atmokpo.com\/w\/35174\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:36:26+00:00","article_modified_time":"2024-11-01T11:44:46+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/35174\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35174\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Kotlin Coding Test Course: Finding the Parent of a Tree","datePublished":"2024-11-01T09:36:26+00:00","dateModified":"2024-11-01T11:44:46+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35174\/"},"wordCount":444,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35174\/","url":"https:\/\/atmokpo.com\/w\/35174\/","name":"Kotlin Coding Test Course: Finding the Parent of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:36:26+00:00","dateModified":"2024-11-01T11:44:46+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35174\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35174\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35174\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Kotlin Coding Test Course: Finding the Parent of a Tree"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35174","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=35174"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35174\/revisions"}],"predecessor-version":[{"id":35175,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35174\/revisions\/35175"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35174"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35174"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35174"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}