{"id":1699,"date":"2020-06-11T11:30:10","date_gmt":"2020-06-11T11:30:10","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1699"},"modified":"2022-03-28T00:24:34","modified_gmt":"2022-03-28T00:24:34","slug":"ancestors","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/ancestors\/","title":{"rendered":"Ancestors"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

DFS , Recursion<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

"<\/code>Lowest common ancestor of two node n1 and n2 is the lowest node in the tree that has both n1 and n2 as descendents(where we allow a node to be a descendant of itself)."<\/code><\/p>\n

Given a binary tree and two values, our task is to return the node which is lowest common ancestor of the two values.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Lowest Common Ancestor (LCA) of two nodes n1<\/code> and n2<\/code> in the tree is the shared ancestor of n1<\/code> and n2<\/code> that is located farthest from the root.<\/p>\n<\/blockquote>\n

Method 1:<\/h4>\n
\n

We can begin by storing path of each node starting from the root one-by-one.<\/p>\n

By the definition of LCA above, we know that there must be some nodes (atleast one), which are common in both the paths we have stored. (Unless the root itself is LCA ).<\/p>\n

Suppose we need to find LCA of the nodes n1<\/code> & n2<\/code>. So,we will search for the nodes n1<\/code> & n2<\/code> in the given tree and store their paths starting from the root node. Now we will start traversing both the path arrays till the values stored in the arrays matches. <\/p>\n

As soon as the values become different we will stop & return the last value which matches both the path arrays. This value is our required LCA.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Method 2 (Efficient):<\/h4>\n
\n

We can reduce the traversal to just once, without using any extra space using following points :<\/p>\n

    \n
  • If root matches any of the values n1<\/code> or n2<\/code>, then root is the LCA<\/strong>.<\/li>\n
  • Else, we will recurvisely call the function for its left<\/strong> & right<\/strong> subtrees. The node which has one value present in its left<\/strong> subtree and the other value present in right<\/strong> subtree is the LCA. <\/li>\n
  • If both values lies in the left<\/strong> subtree, then LCA lies in the left<\/strong> subtree, otherwise LCA lies in right<\/strong> subtree.<\/li>\n<\/ul>\n<\/blockquote>\n

    Complexity Analysis:<\/h3>\n
    \n

    In the first method, although it is O(n)<\/code> in case of time complexity but we are traversing the arrays 3 times (twice for storing the path and once for finding the LCA), with an extra space for path arrays but in the second method we are traversing the array just once also the space complexity is O(1)<\/code> of second method.<\/p>\n<\/blockquote>\n

    SOLUTIONS:<\/h3>\n

    \t\t\t\t\t\t