{"id":3446,"date":"2023-07-24T13:20:12","date_gmt":"2023-07-24T07:50:12","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3446"},"modified":"2023-07-24T13:20:13","modified_gmt":"2023-07-24T07:50:13","slug":"lowest-common-ancestor","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/lowest-common-ancestor\/","title":{"rendered":"Lowest Common Ancestor"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#recursive-approach\">Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#algorithm\">Algorithm<\/a><\/li><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#approach-2-iterative\">Approach 2 (Iterative)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#algorithm\">Algorithm<\/a><\/li><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-will-happen-if-the-tree-is-a-bst\">Q.1: What will happen if the tree is a BST?<\/a><\/li><li><a href=\"#q2-why-is-a-hashmap-used\">Q.2: Why is a Hashmap used?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>The <strong>Lowest Common Ancestor<\/strong> of two nodes is the lowest node that has both nodes as descendants.<\/p>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a binary tree of integers. The task is to find the <strong>Lowest Common Ancestor <\/strong>of two nodes in the given tree.<\/p>\n\n\n\n<p><strong>Examples<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"536\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3483 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-1024x536.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-1024x536.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-300x157.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-768x402.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-380x199.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-550x288.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-800x419.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2.png 1102w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"536\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3484 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-1024x536.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-1024x536.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-300x157.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-768x402.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-380x199.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-550x288.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-800x419.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3.png 1102w\" ><\/figure>\n\n\n\n<h2 id=\"recursive-approach\">Recursive Approach<\/h2>\n\n\n\n<p>The idea is to traverse the <strong>binary tree<\/strong> in a <strong>depth-first <\/strong>approach and search for both nodes in the binary tree. The LCA of both nodes is the node, for which the recursion on the subtree returns the same node.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"867\"  height=\"923\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3486 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 867px) 100vw, 867px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3.png 867w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3-282x300.png 282w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3-768x818.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3-380x405.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3-550x586.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-3-800x852.png 800w\" ><\/figure>\n\n\n\n<h3 id=\"algorithm\"><span id=\"algorithm-2\">Algorithm<\/span><\/h3>\n\n\n\n<ul><li>Start from the <strong>DFS <\/strong>from the <strong>root<\/strong> of the binary tree.<\/li><li>Recurse the <strong>left<\/strong> and <strong>right <\/strong>subtree.<\/li><li>If the current nodes visited is any of the given nodes whose <strong>LCA<\/strong> is to be found, return that node.<\/li><li>Else, for both the nodes, if the subtree provides the same non NULL node, it is the <strong>LCA<\/strong>, hence return the node.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct Node * findLCA(struct Node * root, int n1, int n2) {\n  if (root == NULL) return NULL;\n  if (root -> key == n1 || root -> key == n2)\n    return root;\n \n  Node * left_lca = findLCA(root -> left, n1, n2);\n  Node * right_lca = findLCA(root -> right, n1, n2);\n \n  if (left_lca &amp;&amp; right_lca) return root;\n \n  return (left_lca != NULL) ? left_lca : right_lca;\n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\"><span id=\"java-code-implementation-2\">Java Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">Node root;\n \nNode findLCA(int n1, int n2) {\n  return findLCA(root, n1, n2);\n}\nNode findLCA(Node node, int n1, int n2) {\n  if (node == null)\n    return null;\n \n  if (node.data == n1 || node.data == n2)\n    return node;\n \n  Node left_lca = findLCA(node.left, n1, n2);\n  Node right_lca = findLCA(node.right, n1, n2);\n \n  if (left_lca != null &amp;&amp; right_lca != null)\n    return node;\n \n  return (left_lca != null) ? left_lca : right_lca;\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-2\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def findLCA(root, n1, n2):\n \n    if root is None:\n        return None\n \n    if root.key == n1 or root.key == n2:\n        return root\n \n    left_lca = findLCA(root.left, n1, n2)\n    right_lca = findLCA(root.right, n1, n2)\n \n    if left_lca and right_lca:\n        return root\n \n    return left_lca if left_lca is not None else right_lca<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N) where N is the number of nodes of the binary tree<strong>.<\/strong><\/li><li><strong>Space Complexity: <\/strong>O(N), because of the recursive stack.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-2-iterative\">Approach 2 (Iterative)<\/h2>\n\n\n\n<p>The iterative approach to solve this problem is to use <strong>parent pointers<\/strong>. The idea is to establish <strong>parent pointers <\/strong>for each node so that we can traverse back from the nodes to get their descendants.<\/p>\n\n\n\n<h3 id=\"algorithm\">Algorithm<\/h3>\n\n\n\n<ul><li>Start traversing from the <strong>root <\/strong>node.<\/li><li>For each node visited, keep storing the parent pointers in a <strong>map<\/strong>.<\/li><li>Continue, until both the given nodes are found.<\/li><li>Since all parent points for each node are stored now, traverse back for node1. Similarly, for node2, traverse back through the parent pointers.<\/li><li>If at any point, the same ancestor appears for both nodes, return that node, since it is the <strong>LCA<\/strong> of both nodes.<\/li><li>Else, continue traversing.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">Node * LCA(Node * n1, Node * n2) {\n  map &lt; Node * , bool > ancestors;\n  while (n1 != NULL) {\n    ancestors[n1] = true;\n    n1 = n1 -> parent;\n  }\n  while (n2 != NULL) {\n    if (ancestors.find(n2) != ancestors.end())\n      return n2;\n    n2 = n2 -> parent;\n  }\n \n  return NULL;\n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">Node LCA(Node n1, Node n2) {\n  Map &lt; Node, Boolean > ancestors = new HashMap &lt; Node, Boolean > ();\n  while (n1 != null) {\n    ancestors.put(n1, Boolean.TRUE);\n    n1 = n1.parent;\n  }\n  while (n2 != null) {\n    if (ancestors.containsKey(n2) != ancestors.isEmpty())\n      return n2;\n    n2 = n2.parent;\n  }\n \n  return null;\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def find_lca(n1, n2):\n    seen_on_path: Set[BinaryTreeNode] = set()\n \n    while n1 or n2:\n \n        if n1:\n            if n1 in seen_on_path:\n                return n1\n            seen_on_path.add(n1)\n            n1 = n1.parent\n \n        if n2:\n            if n2 in seen_on_path:\n                return n2\n            seen_on_path.add(n2)\n            n2 = n2.parent\n    return None<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N) where N is the number of nodes of the binary tree<strong>.<\/strong><\/li><li><strong>Space Complexity:<\/strong> O(N), as a map is used.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ol><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/least-common-ancestor\/\" target=\"_blank\">Least Common Ancestor<\/a><\/li><\/ol>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-will-happen-if-the-tree-is-a-bst\"><span id=\"q-1-what-will-happen-if-the-tree-is-a-bst\">Q.1: What will happen if the tree is a BST?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>Though the time complexity will remain the same, for BST, fewer checks need to be done, as we know can apply the property of BST.<\/p>\n\n\n\n<h3 id=\"q2-why-is-a-hashmap-used\"><span id=\"q-2-why-is-a-hashmap-used\">Q.2: Why is a Hashmap used?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The hashmap is used to store the parent pointers of all the nodes so that the nodes can be traversed back and the common ancestors can be found.<\/p>\n","protected":false},"excerpt":{"rendered":"The Lowest Common Ancestor of two nodes is the lowest node that has both nodes as descendants. Problem&hellip;\n","protected":false},"author":5,"featured_media":3485,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[541],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3446"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3446"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3446\/revisions"}],"predecessor-version":[{"id":21859,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3446\/revisions\/21859"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3485"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3446"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3446"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3446"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}