Lowest Common Ancestor of a Binary Tree

Finding the “Lowest Common Ancestor of a Binary Tree” is a very interesting problem. But before going on this code, it is very important to understand the meaning of the problem.

Problem Statement: 

We have given a binary tree and two nodes, node1 and node2. We have to find the lowest common ancestor (LCA) of the given nodes in the binary tree.

So, in this question, we have to find the Lowest Common Ancestor of a Binary Tree, we have given two nodes ( node1 and node2 ) and we have to find the lowest common ancestors between that two nodes. But, while finding the LCA, we have to keep in mind some conditions, which are:

• The binary tree is not necessarily a binary search tree.
• All node values in the binary tree will be unique in the binary tree.
• Both Nodes node1 and node2 will be distinct.

But before starting with the explanation, did you know the meaning of ancestors? If not, then, ancestors are the parent node of the child node.

For example, for the above tree, 

For Node 4: the ancestors are 4,2 and 1. (The node includes itself also).

For node 3, the ancestors are 3 and 1, and for Node 7, the ancestor are 7,3 and 1.

How to find the Lowest Common Ancestor of a Binary Tree?

To find the lowest common ancestor of a binary tree, 

1. We have to first find all the ancestors of both nodes.
2. Then, separate the ancestors that are common in both nodes. 
3. Finally, the lowest common node will be the final answer.

For example, To find LCA for Node 4 and 5 (when both nodes are in the same subtree),

1. Ancestors of Node 4 are 4,2,1
2. Ancestors of Node 5 are 5,2,1
3. Common ancestors of both nodes are 2 and 1.
4. So, the lowest common ancestor is Node 2.
5. So, LCA(4,5)=2

Now, take another example, where both the nodes are in different subtrees. For example, we have to find LCA for nodes 5 and 6. Node 5 is in the left subtree and Node 6 is in the right subtree.

1. So, Ancestors for Node 5 are 5,2,1
2. And, Ancestors for Node 6 are 6,3,1
3. The common ancestor for both the Nde is Node 1.
4. So, LCA(5,6)=1.

I hope you understand how this problem will actually be solved.

Now, let’s move what are the cases we can find in this problem. So, the cases are:

1. The current temporary node can be directly equal to node1 or node2. If it is the case, then we can return the current node. (cur=node1 || cur=node2)
2. node1 is in the left subtree and node2 is in the right subtree or vice versa.
3. Both node1 and node2 are in the same subtree.
4. None of node1 and node2 are in any subtree.

Lowest common ancestor algorithm:

To find the lowest common ancestor of a tree, we can use a recursive algorithm:

1. We will start from the root of the binary tree.
2. If the root is equal to null or matches either of the two given nodes (node1 or node2), return the value of the root itself.
3. The, recursively search for the LCA in the left subtree and right subtree of the root.
4. If both left and right subtrees return non-NULL values, then the root is the LCA.
5. If only one subtree returns a non-NULL value, then the LCA is in that subtree.
6. If both subtrees return NULL values, then the LCA does not exist in the current subtree.

By following this algorithm, we can efficiently find the LCA of any two nodes in the binary tree. 

Code:

#include <iostream>

// Binary Tree Node Structure
struct Node {
    int data;
    Node* left;
    Node* right;

    // Constructor
    Node(int val) {
        data = val;
        left = NULL; 
        right = NULL; 
    }
};

// This is a function to find the Lowest Common Ancestor of two nodes in a binary tree
Node* lca(Node* root, int node1, int node2) {
    if (root == NULL || root->data == node1 || root->data == node2) {
        return root;
    }

    Node* leftLCA = lca(root->left, node1, node2);
    Node* rightLCA = lca(root->right, node1, node2);

    if (leftLCA && rightLCA) {
        return root;
    }

    return (leftLCA != NULL) ? leftLCA : rightLCA; // Replace nullptr with NULL
}

int main() {
    // Constructing a binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // Find the Lowest Common Ancestor of node1 and node2
    Node* lcaNode1 = lca(root, 4, 5);
    Node* lcaNode2 = lca(root, 5, 6);

    std::cout << "Lowest Common Ancestor of 4 and 5 is: " << lcaNode1->data << std::endl;
    std::cout << "Lowest Common Ancestor of 5 and 6 is: " << lcaNode2->data << std::endl;

    return 0;
}

Output:

Code Explanation:

1. First, we will make a binary tree node structure called Node, which will represent each node in the binary tree. And, each Node has an integer data, and two pointers left and right, pointing to its left and right children, respectively.

2. Then, we will make a constructor for the Node class that initializes a node with the given val. And then, set the data member to the input val, and left and right pointers are initialized to NULL value which indicates that the node has no children initially.

3. Next, the code defines the “lca” function, which is the main function to find the Lowest Common Ancestor of two nodes in a binary tree. This function will take three parameters:

   – root: A pointer to the root of the binary tree or a subtree.

   – node1: The value of the first node for which we want to find the LCA.

   – node2: The value of the second node for which we want to find the LCA.

4. Inside the lca function, we will do several recursive calls to the lca function to traverse the binary tree and find the LCA. This function will follow a depth-first search (DFS) approach to explore the tree.

5. Then, we will check several conditions like:

• If the current root is equal to null. 
• Or if its data matches either node1 or node2.  
• If any of these conditions are true, it means we have either reached the end of a branch or found one of the two nodes we are looking for. In such cases, the function will return the current root value, which will be either one of the two nodes or a null node.

6. After that, this function will make recursive calls to itself for the left and right subtrees of the current root, searching for node1 and node2.

7. If the nodes were found, then the function stores the results of the recursive calls in leftLCA and rightLCA.

8. If both leftLCA and rightLCA are not equal to null, it means node1 and node2 are found in different subtrees of the current root, and the current root is the LCA. So, the function returns the current root value.

9. If only one of leftLCA or rightLCA is null, it means either node1 or node2 is found in one of the subtrees. In this case, the function returns the non-null value as the LCA.

10. If both leftLCA and rightLCA are null, it means neither node1 nor node2 is found in the current subtree, so the function returns null.

11. Then we will construct a sample binary tree and call the lca function to find the LCA of two pairs of nodes: (4, 5) and (5, 6).

12. Finally, the code prints the results, which are the data values of the LCA nodes.