Lowest Common Ancestor (LCA) in a Binary Tree is a fundamental concept in computer science and is widely used in various applications such as data compression, phylogenetics, and bioinformatics. The LCA of two nodes in a binary tree is the node that is the lowest in the tree and is an ancestor of both nodes. In this article, we will discuss the concept of LCA in a binary tree and its implementation in C++.
A binary tree is a tree data structure in which each node has at most two children. The root of the tree is the topmost node and the children of a node are referred to as its left and right child. The LCA of two nodes in a binary tree can be found by traversing the tree from the root node and comparing the values of the current node with the values of the two nodes for which we want to find the LCA. If the current node is equal to either of the two nodes, then it is the LCA. If the current node is not equal to either of the two nodes, then we recursively traverse the left and right subtrees of the current node and repeat the process.
There are several different algorithms that can be used to find the LCA in a binary tree, but the most common and efficient algorithm is the Tarjan's Algorithm. This algorithm is based on the observation that if two nodes are in the same subtree, then their LCA is in that subtree as well. The algorithm starts at the root of the tree and recursively traverses the left and right subtrees of the current node, comparing the values of the current node with the values of the two nodes for which we want to find the LCA. If the current node is equal to either of the two nodes, then it is the LCA. If the current node is not equal to either of the two nodes, then we recursively traverse the left and right subtrees of the current node and repeat the process.
The Tarjan's Algorithm can be implemented in C++ using the following code:
#include <iostream> using namespace std; struct Node { int data; Node* left; Node* right; };
Node* newNode(int data) { Node* node = new Node(); node->data = data; node->left = NULL; node->right = NULL; return node; } Node* findLCA(Node* root, int n1, int n2) {
if (root == NULL) return NULL; if (root->data == n1 || root->data == n2) return root; Node* left_lca = findLCA(root->left, n1, n2); Node* right_lca = findLCA(root->right, n1, n2); if (left_lca && right_lca) return root; return (left_lca != NULL) ? left_lca : right_lca; }
int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); cout << "LCA(4, 5)= " << findLCA(root, 4, 5)->data << endl; cout << "LCA(4, 6) = " << findLCA(root, 4, 6)->data << endl; cout << "LCA(3, 4) = " << findLCA(root, 3, 4)->data << endl; cout << "LCA(2, 4) = " << findLCA(root, 2, 4)->data << endl; return 0; }
In this code, we first define a struct `Node` that represents a node in the binary tree. Each node contains an integer data value, and pointers to its left and right children. We then define a function `newNode` which creates a new node with the given data value and initializes its left and right children to NULL. The main function of the algorithm is the `findLCA` function, which takes as input the root of the binary tree, and the values of the two nodes for which we want to find the LCA. The function starts by checking if the current node is NULL, and if so, it returns NULL. If the current node is equal to either of the two nodes, then it is the LCA and the function returns the current node. If the current node is not equal to either of the two nodes, then the function recursively calls itself on the left and right subtrees of the current node, and stores the result in the variables `left_lca` and `right_lca`. If both `left_lca` and `right_lca` are not NULL, then the current node is the LCA and the function returns the current node. If only one of `left_lca` and `right_lca` is not NULL, then the function returns that variable, as it represents the LCA.
The Tarjan's Algorithm has a time complexity of O(n), where n is the number of nodes in the binary tree. This is because the algorithm visits each node in the tree exactly once. The space complexity of the algorithm is also O(n), as the maximum number of function calls on the call stack is equal to the number of nodes in the tree.
In addition to the Tarjan's Algorithm, there are other algorithms that can be used to find the LCA in a binary tree such as the Euler Tour Algorithm and the DFS Algorithm. The Euler Tour Algorithm is based on the observation that the LCA of two nodes in a binary tree can be found by finding the lowest node on the Euler Tour of the tree that is an ancestor of both nodes. The Euler Tour of a tree is a linear representation of the tree in which each node is visited twice, once when entering the node and once when leaving the node. The DFS Algorithm is based on the observation that the LCA of two nodes in a binary tree can be found by doing a depth-first search of the tree, and keeping track of the ancestors of the two nodes.
In conclusion, the Lowest Common Ancestor (LCA) in a Binary Tree is a fundamental concept in computer science and is widely used in various applications such as data compression, phylogenetics, and bioinformatics. The Tarjan's Algorithm is the most common and efficient algorithm for finding the LCA in a binary tree. It has a time complexity of O(n) and a space complexity of O(n). Other algorithms that can be used to find the LCA in a binary tree include the Euler Tour Algorithm and the D
