{"id":33496,"date":"2024-11-01T09:17:07","date_gmt":"2024-11-01T09:17:07","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33496"},"modified":"2024-11-01T11:38:22","modified_gmt":"2024-11-01T11:38:22","slug":"java-coding-test-course-finding-the-lowest-common-ancestor-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33496\/","title":{"rendered":"Java Coding Test Course, Finding the Lowest Common Ancestor 2"},"content":{"rendered":"<div class=\"post\">\n<h2>Problem Description<\/h2>\n<p>\n        The problem of finding the Lowest Common Ancestor (LCA) of two nodes in a given binary tree is an important topic in various algorithm problem solving. This problem particularly requires understanding of tree structures and recursive thinking. In this article, we will take a deep dive into how to find the Lowest Common Ancestor.\n    <\/p>\n<h3>Problem Definition<\/h3>\n<p>\n        Given a root node of a binary tree and two nodes A and B, you need to solve the problem of finding the Lowest Common Ancestor of A and B. The Lowest Common Ancestor is defined as the deepest (lowest) node that satisfies the following conditions:\n    <\/p>\n<ul>\n<li>It must include all ancestors of nodes A and B.<\/li>\n<li>The node LCA must exist within the subtree where A and B are located.<\/li>\n<\/ul>\n<h3>Constraints<\/h3>\n<p>\n        The given binary tree has the following constraints:\n    <\/p>\n<ul>\n<li>The number of nodes is between 1 and 10^4.<\/li>\n<li>Each node has a unique value.<\/li>\n<li>Both A and B must be nodes that exist in the tree.<\/li>\n<\/ul>\n<h2>Problem Solving Strategy<\/h2>\n<h3>1. Understanding Tree Structure<\/h3>\n<p>\n        A tree is a hierarchical data structure composed of nodes and edges. In the case of a binary tree, each node can have at most two children. To find the Lowest Common Ancestor based on the depth of the tree, we need to acquire the following resources.\n    <\/p>\n<h3>2. Algorithm Selection<\/h3>\n<p>\n        We can use DFS (Depth-First Search) as the candidate algorithm. This approach involves the following steps:\n    <\/p>\n<ol>\n<li>Start from the root node and explore the left and right subtrees.<\/li>\n<li>If both nodes A and B exist in their respective subtrees, the current node becomes the LCA.<\/li>\n<li>If either A or B exists in only one subtree, return that node.<\/li>\n<li>If neither exists, return null.<\/li>\n<\/ol>\n<h2>Python Implementation<\/h2>\n<pre><code>\n# Definition of a binary tree node\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\n# Finding LCA\ndef lowestCommonAncestor(root, p, q):\n    if root is None:\n        return None\n    \n    if root == p or root == q:\n        return root\n    \n    left = lowestCommonAncestor(root.left, p, q)\n    right = lowestCommonAncestor(root.right, p, q)\n    \n    if left and right:\n        return root\n    return left if left else right\n    <\/code><\/pre>\n<h2>Implementation Explanation<\/h2>\n<h3>1. TreeNode Class<\/h3>\n<p>\n        First, we define the TreeNode class to store the value of each node. Each node references its left (left) and right (right) child nodes, in addition to its value (val).\n    <\/p>\n<h3>2. lowestCommonAncestor Function<\/h3>\n<p>\n        Starting from the given root node, we recursively call the function to find the LCA of the two nodes A and B. The base cases are when the node is null or the root is A or B, in which case we return the current node.\n    <\/p>\n<p>\n        Since we are looking for the LCA in each subtree, if both values returned from the left and right subtrees exist, the current node is the LCA.\n    <\/p>\n<h3>3. Problem Solving<\/h3>\n<p>\n        Now, we can use this algorithm to find the LCA for the two nodes A and B in the given binary tree. The time complexity of the algorithm is O(N), where N is the number of nodes.\n    <\/p>\n<h2>Performance Validation<\/h2>\n<p>\n        We can test this algorithm with various inputs to validate its performance. For example, we can consider the following binary tree as input.\n    <\/p>\n<pre><code>\n    # Example tree creation\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    p = root.left         # Node with value 5\n    q = root.left.right.right  # Node with value 4\n\n    ancestor = lowestCommonAncestor(root, p, q)\n    print(ancestor.val)  # Expected output: 5\n    <\/code><\/pre>\n<h2>Conclusion<\/h2>\n<p>\n        In this lecture, we thoroughly covered finding the Lowest Common Ancestor, which is one of the important concepts in Java coding tests. This algorithm can be utilized in various situations and is very helpful for understanding tree structures. I hope the problem-solving process and algorithm analysis will assist you in preparing for coding tests.\n    <\/p>\n<p>\n        If you have any additional questions, please leave them in the comments. Thank you!\n    <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem Description The problem of finding the Lowest Common Ancestor (LCA) of two nodes in a given binary tree is an important topic in various algorithm problem solving. This problem particularly requires understanding of tree structures and recursive thinking. In this article, we will take a deep dive into how to find the Lowest Common &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33496\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Java Coding Test Course, Finding the Lowest 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":[139],"tags":[],"class_list":["post-33496","post","type-post","status-publish","format-standard","hentry","category-java-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Java Coding Test Course, Finding the Lowest 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\/33496\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Java Coding Test Course, Finding the Lowest Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Problem Description The problem of finding the Lowest Common Ancestor (LCA) of two nodes in a given binary tree is an important topic in various algorithm problem solving. This problem particularly requires understanding of tree structures and recursive thinking. In this article, we will take a deep dive into how to find the Lowest Common &hellip; \ub354 \ubcf4\uae30 &quot;Java Coding Test Course, Finding the Lowest Common Ancestor 2&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33496\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:17:07+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:38:22+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\/33496\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33496\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, Finding the Lowest Common Ancestor 2\",\"datePublished\":\"2024-11-01T09:17:07+00:00\",\"dateModified\":\"2024-11-01T11:38:22+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33496\/\"},\"wordCount\":534,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33496\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33496\/\",\"name\":\"Java Coding Test Course, Finding the Lowest Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:17:07+00:00\",\"dateModified\":\"2024-11-01T11:38:22+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33496\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33496\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33496\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java Coding Test Course, Finding the Lowest 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":"Java Coding Test Course, Finding the Lowest 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\/33496\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, Finding the Lowest Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Problem Description The problem of finding the Lowest Common Ancestor (LCA) of two nodes in a given binary tree is an important topic in various algorithm problem solving. This problem particularly requires understanding of tree structures and recursive thinking. In this article, we will take a deep dive into how to find the Lowest Common &hellip; \ub354 \ubcf4\uae30 \"Java Coding Test Course, Finding the Lowest Common Ancestor 2\"","og_url":"https:\/\/atmokpo.com\/w\/33496\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:17:07+00:00","article_modified_time":"2024-11-01T11:38:22+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\/33496\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33496\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, Finding the Lowest Common Ancestor 2","datePublished":"2024-11-01T09:17:07+00:00","dateModified":"2024-11-01T11:38:22+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33496\/"},"wordCount":534,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33496\/","url":"https:\/\/atmokpo.com\/w\/33496\/","name":"Java Coding Test Course, Finding the Lowest Common Ancestor 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:17:07+00:00","dateModified":"2024-11-01T11:38:22+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33496\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33496\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33496\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java Coding Test Course, Finding the Lowest 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\/33496","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=33496"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33496\/revisions"}],"predecessor-version":[{"id":33497,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33496\/revisions\/33497"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33496"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33496"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}