{"id":34860,"date":"2024-11-01T09:32:50","date_gmt":"2024-11-01T09:32:50","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34860"},"modified":"2024-11-01T11:26:13","modified_gmt":"2024-11-01T11:26:13","slug":"swift-coding-test-course-finding-the-least-common-ancestor-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34860\/","title":{"rendered":"Swift Coding Test Course, Finding the Least Common Ancestor 2"},"content":{"rendered":"<div class=\"post\">\n<p>Hello! Today, we will tackle the problem of finding the Lowest Common Ancestor (LCA) in Swift coding tests for those preparing for it. This problem involves finding the closest common ancestor of two nodes in a tree structure and has various applications. It is also one of the frequently appearing problems in coding tests.<\/p>\n<h2>Problem Description<\/h2>\n<p>When given a binary tree with two nodes, write a function to find the lowest common ancestor of these two nodes. The nodes of the binary tree are defined as follows:<\/p>\n<pre>\n    class TreeNode {\n        var value: Int\n        var left: TreeNode?\n        var right: TreeNode?\n        \n        init(value: Int) {\n            self.value = value\n            self.left = nil\n            self.right = nil\n        }\n    }\n    <\/pre>\n<p>For example, consider the following binary tree:<\/p>\n<pre>\n          3\n         \/ \\\n        5   1\n       \/ \\ \/ \\\n      6  2 0  8\n        \/ \\\n       7   4\n    <\/pre>\n<p>The lowest common ancestor of node 5 and node 1 is node 3. In the case of node 5 and node 4, the lowest common ancestor is node 5.<\/p>\n<h2>Input Format<\/h2>\n<p>The function is defined in the following format:<\/p>\n<pre>\n    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode?\n    <\/pre>\n<p>Here, <code>root<\/code> is the root node of the binary tree, and <code>p<\/code> and <code>q<\/code> represent the respective nodes. These nodes exist in the tree.<\/p>\n<h2>Solution Process<\/h2>\n<p>There are various approaches to solve this problem, but one of the most efficient methods is to use recursion. Below, I will explain the process of solving the problem using this method step-by-step.<\/p>\n<h3>Step 1: Basic Idea<\/h3>\n<p>Through tree traversal, we can consider the following three cases for each node:<\/p>\n<ul>\n<li>If the current node matches <code>p<\/code> or <code>q<\/code><\/li>\n<li>If we are searching for <code>p<\/code> or <code>q<\/code> in the left subtree<\/li>\n<li>If we are searching for <code>p<\/code> or <code>q<\/code> in the right subtree<\/li>\n<\/ul>\n<p>Through these cases, we can deduce the lowest common ancestor. If we find one node in each of the two subtrees, the current node is the lowest common ancestor.<\/p>\n<h3>Step 2: Implementing the Recursive Function<\/h3>\n<p>Now, we implement a recursive function to find the two nodes at each node:<\/p>\n<pre>\n    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {\n        \/\/ If the node to check is nil\n        guard let current = root else { return nil }\n\n        \/\/ If the current node is p or q\n        if current === p || current === q {\n            return current\n        }\n\n        \/\/ Search for the respective nodes in the left and right subtrees\n        let left = lowestCommonAncestor(current.left, p, q)\n        let right = lowestCommonAncestor(current.right, p, q)\n\n        \/\/ If we found one in both the left and right subtrees\n        if left != nil && right != nil {\n            return current\n        }\n\n        \/\/ If we found one only in one subtree\n        return left ?? right\n    }\n    <\/pre>\n<p>In the code above, we check whether the current node is nil using the <code>guard let<\/code> statement and test whether the current node matches <code>p<\/code> or <code>q<\/code>. After that, we recursively call the function on the left and right subtrees and store the results in <code>left<\/code> and <code>right<\/code>. If we find results in both subtrees, we return the current node as the lowest common ancestor.<\/p>\n<h3>Step 3: Writing Test Cases<\/h3>\n<p>Now, we will add some test cases to test the function we wrote:<\/p>\n<pre>\n    let root = TreeNode(value: 3)\n    let node5 = TreeNode(value: 5)\n    let node1 = TreeNode(value: 1)\n    let node6 = TreeNode(value: 6)\n    let node2 = TreeNode(value: 2)\n    let node0 = TreeNode(value: 0)\n    let node8 = TreeNode(value: 8)\n    let node7 = TreeNode(value: 7)\n    let node4 = TreeNode(value: 4)\n\n    \/\/ Connecting the tree structure\n    root.left = node5\n    root.right = node1\n    node5.left = node6\n    node5.right = node2\n    node1.left = node0\n    node1.right = node8\n    node2.left = node7\n    node2.right = node4\n\n    \/\/ Testing\n    let lca1 = lowestCommonAncestor(root, node5, node1) \/\/ Result should be 3\n    let lca2 = lowestCommonAncestor(root, node5, node4) \/\/ Result should be 5\n    <\/pre>\n<p>We execute the test cases to check the results. In this case, we validate whether the expected results come out and whether each node&#8217;s lowest common ancestor is found correctly.<\/p>\n<h2>Time Complexity Analysis<\/h2>\n<p>The time complexity of this algorithm is O(N). This is because, in the worst case, we may need to traverse all nodes; thus, it takes up to O(N) time for a tree with N nodes. Additionally, the space complexity is O(H), where H represents the depth of the tree. This refers to the depth of the recursive call stack.<\/p>\n<h2>Conclusion<\/h2>\n<p>Today, we learned how to solve the problem of finding the lowest common ancestor in a binary tree using Swift. This problem frequently appears in coding tests, so it is important to develop the skill to solve problems quickly when they arise. By utilizing a recursive approach to solve the problem, we improved the efficiency of the code and emphasized the understanding. I will return with another interesting algorithmic problem next time!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello! Today, we will tackle the problem of finding the Lowest Common Ancestor (LCA) in Swift coding tests for those preparing for it. This problem involves finding the closest common ancestor of two nodes in a tree structure and has various applications. It is also one of the frequently appearing problems in coding tests. Problem &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34860\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Swift Coding Test Course, Finding the Least Common Ancestor 2&#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":[129],"tags":[],"class_list":["post-34860","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Swift Coding Test Course, Finding the Least Common Ancestor 2 - \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\/34860\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Swift Coding Test Course, Finding the Least Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! Today, we will tackle the problem of finding the Lowest Common Ancestor (LCA) in Swift coding tests for those preparing for it. This problem involves finding the closest common ancestor of two nodes in a tree structure and has various applications. It is also one of the frequently appearing problems in coding tests. Problem &hellip; \ub354 \ubcf4\uae30 &quot;Swift Coding Test Course, Finding the Least Common Ancestor 2&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34860\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:32:50+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:26:13+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=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34860\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34860\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Finding the Least Common Ancestor 2\",\"datePublished\":\"2024-11-01T09:32:50+00:00\",\"dateModified\":\"2024-11-01T11:26:13+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34860\/\"},\"wordCount\":527,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34860\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34860\/\",\"name\":\"Swift Coding Test Course, Finding the Least Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:32:50+00:00\",\"dateModified\":\"2024-11-01T11:26:13+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34860\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34860\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34860\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Finding the Least Common Ancestor 2\"}]},{\"@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":"Swift Coding Test Course, Finding the Least Common Ancestor 2 - \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\/34860\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Finding the Least Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! Today, we will tackle the problem of finding the Lowest Common Ancestor (LCA) in Swift coding tests for those preparing for it. This problem involves finding the closest common ancestor of two nodes in a tree structure and has various applications. It is also one of the frequently appearing problems in coding tests. Problem &hellip; \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Finding the Least Common Ancestor 2\"","og_url":"https:\/\/atmokpo.com\/w\/34860\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:32:50+00:00","article_modified_time":"2024-11-01T11:26:13+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":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34860\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34860\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Finding the Least Common Ancestor 2","datePublished":"2024-11-01T09:32:50+00:00","dateModified":"2024-11-01T11:26:13+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34860\/"},"wordCount":527,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34860\/","url":"https:\/\/atmokpo.com\/w\/34860\/","name":"Swift Coding Test Course, Finding the Least Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:32:50+00:00","dateModified":"2024-11-01T11:26:13+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34860\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34860\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34860\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Finding the Least Common Ancestor 2"}]},{"@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\/34860","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=34860"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34860\/revisions"}],"predecessor-version":[{"id":34861,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34860\/revisions\/34861"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34860"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34860"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34860"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}