{"id":33766,"date":"2024-11-01T09:20:09","date_gmt":"2024-11-01T09:20:09","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33766"},"modified":"2024-11-01T11:46:46","modified_gmt":"2024-11-01T11:46:46","slug":"python-coding-test-course-least-common-ancestor","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33766\/","title":{"rendered":"python coding test course, least common ancestor"},"content":{"rendered":"<div class=\"post\">\n<p>Hello! In this lecture, we will discuss one of the algorithm problems known as &#8216;Lowest Common Ancestor (LCA)&#8217;. The LCA problem involves finding the closest common ancestor of two given nodes in a tree structure. This problem is very important in various fields and is often asked in many interviews.<\/p>\n<h2>Problem Description<\/h2>\n<p>Given the value of two nodes in a binary tree (including binary search trees), find their lowest common ancestor.<\/p>\n<h3>Input<\/h3>\n<ul>\n<li>Number of nodes N (1 \u2264 N \u2264 1000)<\/li>\n<li>Values of N nodes<\/li>\n<li>Two node values A, B (A and B must exist in the tree)<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<p>Output the value of the lowest common ancestor of the two nodes.<\/p>\n<h2>Understanding the Problem<\/h2>\n<p>The Lowest Common Ancestor problem helps in understanding the characteristics of the data structure that makes up the tree and the relationships between nodes. A common ancestor refers to a node that two nodes meet at while moving up. For example, let&#8217;s consider the tree below.<\/p>\n<pre>\n              3\n            \/   \\\n          5      1\n         \/ \\    \/ \\\n        6   2  0   8\n           \/ \\\n          7   4\n    <\/pre>\n<p>In this tree, the lowest common ancestor of nodes 5 and 1 is 3, and the lowest common ancestor of nodes 6 and 4 is 5.<\/p>\n<h2>Solution Strategy<\/h2>\n<p>The basic method to find the lowest common ancestor is as follows:<\/p>\n<ol>\n<li>Traverse the tree and store the paths of the given two nodes.<\/li>\n<li>Find the last common node in both paths.<\/li>\n<\/ol>\n<p>This method is intuitive and straightforward, but it can be inefficient in some cases. Instead, a more efficient method can be used as described below.<\/p>\n<h3>Efficient Method<\/h3>\n<p>An efficient way to find the LCA in a binary tree is to use Depth First Search (DFS). This method recursively explores nodes with the given values, and when both nodes are found, it returns that node.<\/p>\n<h2>Code Implementation<\/h2>\n<p>Now we will implement this algorithm in Python. Below is the code to find the LCA:<\/p>\n<pre><code>\nclass TreeNode:\n    def __init__(self, x):\n        self.val = x\n        self.left = None\n        self.right = None\n\ndef lowest_common_ancestor(root, p, q):\n    # Base condition\n    if not root or root == p or root == q:\n        return root\n\n    # Recursively look for LCA in left and right\n    left = lowest_common_ancestor(root.left, p, q)\n    right = lowest_common_ancestor(root.right, p, q)\n\n    # If both child nodes exist\n    if left and right:\n        return root\n    return left if left else right\n\n# Test case\nif __name__ == \"__main__\":\n    # Constructing the tree\n    root = TreeNode(3)\n    root.left = TreeNode(5)\n    root.right = TreeNode(1)\n    root.left.left = TreeNode(6)\n    root.left.right = TreeNode(2)\n    root.right.left = TreeNode(0)\n    root.right.right = TreeNode(8)\n    root.left.right.left = TreeNode(7)\n    root.left.right.right = TreeNode(4)\n\n    # Setting nodes p and q\n    p = root.left  # 5\n    q = root.right  # 1\n\n    # Calculating LCA\n    lca = lowest_common_ancestor(root, p, q)\n    print(f\"Lowest Common Ancestor: {lca.val}\")\n    <\/code><\/pre>\n<h2>Algorithm Analysis<\/h2>\n<p>This algorithm visits each node in the tree only once, therefore the time complexity is O(N), and the space complexity is O(H), where N is the number of nodes and H is the height of the tree. In the worst case, H can be equal to N, resulting in an overall time and space complexity of O(N).<\/p>\n<h2>Conclusion<\/h2>\n<p>In this lecture, we learned about the Lowest Common Ancestor problem. Although this problem requires considering many cases, it can be solved simply with the correct algorithm. When solving actual problems, it is essential to have a solid understanding of the tree structure and the relationships between nodes. In the next lecture, we will cover another algorithm problem. Thank you!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello! In this lecture, we will discuss one of the algorithm problems known as &#8216;Lowest Common Ancestor (LCA)&#8217;. The LCA problem involves finding the closest common ancestor of two given nodes in a tree structure. This problem is very important in various fields and is often asked in many interviews. Problem Description Given the value &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33766\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;python coding test course, least common ancestor&#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":[145],"tags":[],"class_list":["post-33766","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>python coding test course, least common ancestor - \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\/33766\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"python coding test course, least common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this lecture, we will discuss one of the algorithm problems known as &#8216;Lowest Common Ancestor (LCA)&#8217;. The LCA problem involves finding the closest common ancestor of two given nodes in a tree structure. This problem is very important in various fields and is often asked in many interviews. Problem Description Given the value &hellip; \ub354 \ubcf4\uae30 &quot;python coding test course, least common ancestor&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33766\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:20:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:46: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=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33766\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33766\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"python coding test course, least common ancestor\",\"datePublished\":\"2024-11-01T09:20:09+00:00\",\"dateModified\":\"2024-11-01T11:46:46+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33766\/\"},\"wordCount\":423,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33766\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33766\/\",\"name\":\"python coding test course, least common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:20:09+00:00\",\"dateModified\":\"2024-11-01T11:46:46+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33766\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33766\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33766\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"python coding test course, least common ancestor\"}]},{\"@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":"python coding test course, least common ancestor - \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\/33766\/","og_locale":"ko_KR","og_type":"article","og_title":"python coding test course, least common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this lecture, we will discuss one of the algorithm problems known as &#8216;Lowest Common Ancestor (LCA)&#8217;. The LCA problem involves finding the closest common ancestor of two given nodes in a tree structure. This problem is very important in various fields and is often asked in many interviews. Problem Description Given the value &hellip; \ub354 \ubcf4\uae30 \"python coding test course, least common ancestor\"","og_url":"https:\/\/atmokpo.com\/w\/33766\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:20:09+00:00","article_modified_time":"2024-11-01T11:46: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":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33766\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33766\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"python coding test course, least common ancestor","datePublished":"2024-11-01T09:20:09+00:00","dateModified":"2024-11-01T11:46:46+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33766\/"},"wordCount":423,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33766\/","url":"https:\/\/atmokpo.com\/w\/33766\/","name":"python coding test course, least common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:20:09+00:00","dateModified":"2024-11-01T11:46:46+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33766\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33766\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33766\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"python coding test course, least common ancestor"}]},{"@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\/33766","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=33766"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33766\/revisions"}],"predecessor-version":[{"id":33767,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33766\/revisions\/33767"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33766"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33766"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}