Adding Lowest Common Ancestor of a Binary Tree (using C, C++, Python)

[Maheshmali1]

Feature to be added : Lowest Common Ancestor of a Binary Tree (using C, C++, Python)

Describe the solution :

The Lowest Common Ancestor (LCA) algorithm is used to find the lowest common ancestor of two nodes in a tree. The lowest common ancestor is the deepest node that is a common ancestor of both given nodes. This algorithm is widely used in various applications, including data structures, graph algorithms, and tree-related problems.

Algorithm flow :

• The algorithm takes three parameters: root, node1, and node2, representing the root of the tree and the two nodes for which we want to find the LCA.
• The base case checks if the root is null or matches either node1 or node2. If it does, we return the root since it is the LCA in these cases.
• Recursively, we find the LCA in the left and right subtrees by calling the findLCA function on them.
• We store the results of the recursive calls in leftLCA and rightLCA.
• If both leftLCA and rightLCA are not null, it means that node1 and node2 are found in different subtrees, so the current root is the LCA.
• Otherwise, we return the non-null LCA (if any). If leftLCA is not null, it means both node1 and node2 are in the left subtree, so we return leftLCA. Otherwise, we return rightLCA if it is not null.

I searched across our algorithms repository but couldn’t find this algorithm and its important Algorithm that we are missing.

Please assign me this issue under SSoC23

[Maheshmali1]

@Kumar-laxmi Please assign me this issue. Thanks.

[Maheshmali1]

@Kumar-laxmi Please assign me this issue. Suggest any improvements needed but please respond.

[Maheshmali1]

@Kumar-laxmi Please respond to this issue.

[github-actions[bot]]

Stale issue message