{"id":34418,"date":"2024-11-01T09:27:54","date_gmt":"2024-11-01T09:27:54","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34418"},"modified":"2024-11-01T11:41:20","modified_gmt":"2024-11-01T11:41:20","slug":"javascript-coding-test-course-lowest-common-ancestor","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34418\/","title":{"rendered":"JavaScript Coding Test Course, Lowest Common Ancestor"},"content":{"rendered":"<p>Hello, everyone! In this post, we will explore the &#8216;Least Common Ancestor (LCA)&#8217; problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process.<\/p>\n<h2>Problem Description<\/h2>\n<p>This is the problem of finding the least common ancestor of two nodes in a given binary tree. The tree follows these rules:<\/p>\n<ul>\n<li>Each node can have at most two children.<\/li>\n<li>The given two nodes always exist in the tree.<\/li>\n<\/ul>\n<h3>Input<\/h3>\n<ul>\n<li>Address of the root node of the tree (root)<\/li>\n<li>Address of the first node (node1)<\/li>\n<li>Address of the second node (node2)<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<p>Print the node value of the least common ancestor of the two nodes.<\/p>\n<h2>Example<\/h2>\n<pre><code>Input:\n          3\n         \/ \\\n        5   1\n       \/ \\ \/ \\\n      6  2 0  8\n        \/ \\\n       7   4\n       \n       node1 = 5, node2 = 1\n       \nOutput:\n3\n<\/code><\/pre>\n<h2>Solution<\/h2>\n<p>There can be several approaches to solve this problem. However, the most common approach is to use DFS (Depth First Search). This method allows us to find the least common ancestor by visiting each node. Let\u2019s examine this process step by step.<\/p>\n<h3>Step 1: Define the Tree Structure<\/h3>\n<p>First, we need to create a class defining the tree. In JavaScript, a tree node can generally be defined as follows:<\/p>\n<pre><code>class TreeNode {\n    constructor(value) {\n        this.value = value;\n        this.left = null; \/\/ left child\n        this.right = null; \/\/ right child\n    }\n}\n<\/code><\/pre>\n<h3>Step 2: Create the Tree<\/h3>\n<p>Let&#8217;s write sample code to create the tree. The following code creates a tree like the one in the example above:<\/p>\n<pre><code>const root = new TreeNode(3);\nroot.left = new TreeNode(5);\nroot.right = new TreeNode(1);\nroot.left.left = new TreeNode(6);\nroot.left.right = new TreeNode(2);\nroot.right.left = new TreeNode(0);\nroot.right.right = new TreeNode(8);\nroot.left.right.left = new TreeNode(7);\nroot.left.right.right = new TreeNode(4);\n<\/code><\/pre>\n<h3>Step 3: Implement the DFS Algorithm<\/h3>\n<p>Now it\u2019s time to implement the DFS algorithm. The process for finding the least common ancestor follows these steps:<\/p>\n<ol>\n<li>If the current node is null, return null.<\/li>\n<li>If the current node is equal to node1 or node2, return the current node.<\/li>\n<li>Recursively call the left and right children to obtain the results.<\/li>\n<li>If both left and right child node results are not null, the current node is the least common ancestor.<\/li>\n<li>If only one of the left or right children is not null, return the non-null child.<\/li>\n<\/ol>\n<pre><code>function lowestCommonAncestor(root, node1, node2) {\n    if (root === null) return null;\n    if (root.value === node1.value || root.value === node2.value) return root;\n\n    const left = lowestCommonAncestor(root.left, node1, node2);\n    const right = lowestCommonAncestor(root.right, node1, node2);\n\n    if (left && right) return root;\n    return left ? left : right;\n}\n<\/code><\/pre>\n<h3>Step 4: Output the Result<\/h3>\n<p>Now that the least common ancestor algorithm is complete, let\u2019s test it:<\/p>\n<pre><code>const lca = lowestCommonAncestor(root, root.left, root.right); \/\/ node1: 5, node2: 1\nconsole.log(lca.value); \/\/ 3\n<\/code><\/pre>\n<h2>Summary and Conclusion<\/h2>\n<p>In this post, we covered the Least Common Ancestor (LCA) problem. We defined the tree structure, implemented an algorithm using DFS, and verified the results through examples. The key point is that this algorithm visits each node through recursive calls, structurally setting conditions to find the least common ancestor.<\/p>\n<p>Such problems have various forms, so it is important to practice solving different types of problems. We will continue to introduce various algorithms that will help you prepare for JavaScript coding tests, so please stay tuned!<\/p>\n<h2>References<\/h2>\n<ul>\n<li><a href=\"https:\/\/www.geeksforgeeks.org\/lowest-common-ancestor-in-a-binary-tree\/\">GeeksforGeeks &#8211; Lowest Common Ancestor in a Binary Tree<\/a><\/li>\n<li><a href=\"https:\/\/www.programcreek.com\/2012\/12\/leetcode-lowest-common-ancestor-of-a-binary-tree\/\">ProgramCreek &#8211; LeetCode: Lowest Common Ancestor of a Binary Tree<\/a><\/li>\n<\/ul>\n<p>I hope this helps you prepare for your coding tests. Thank you!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello, everyone! In this post, we will explore the &#8216;Least Common Ancestor (LCA)&#8217; problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process. Problem Description This &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34418\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;JavaScript Coding Test Course, Lowest 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":[141],"tags":[],"class_list":["post-34418","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>JavaScript Coding Test Course, Lowest 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\/34418\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"JavaScript Coding Test Course, Lowest Common Ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello, everyone! In this post, we will explore the &#8216;Least Common Ancestor (LCA)&#8217; problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process. Problem Description This &hellip; \ub354 \ubcf4\uae30 &quot;JavaScript Coding Test Course, Lowest Common Ancestor&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34418\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:27:54+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:41:20+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\/34418\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34418\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Lowest Common Ancestor\",\"datePublished\":\"2024-11-01T09:27:54+00:00\",\"dateModified\":\"2024-11-01T11:41:20+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34418\/\"},\"wordCount\":464,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34418\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34418\/\",\"name\":\"JavaScript Coding Test Course, Lowest Common Ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:27:54+00:00\",\"dateModified\":\"2024-11-01T11:41:20+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34418\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34418\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34418\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Lowest 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":"JavaScript Coding Test Course, Lowest 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\/34418\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Lowest Common Ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello, everyone! In this post, we will explore the &#8216;Least Common Ancestor (LCA)&#8217; problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process. Problem Description This &hellip; \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Lowest Common Ancestor\"","og_url":"https:\/\/atmokpo.com\/w\/34418\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:27:54+00:00","article_modified_time":"2024-11-01T11:41:20+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\/34418\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34418\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Lowest Common Ancestor","datePublished":"2024-11-01T09:27:54+00:00","dateModified":"2024-11-01T11:41:20+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34418\/"},"wordCount":464,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34418\/","url":"https:\/\/atmokpo.com\/w\/34418\/","name":"JavaScript Coding Test Course, Lowest Common Ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:27:54+00:00","dateModified":"2024-11-01T11:41:20+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34418\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34418\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34418\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Lowest 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\/34418","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=34418"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34418\/revisions"}],"predecessor-version":[{"id":34419,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34418\/revisions\/34419"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34418"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34418"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34418"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}