LCA of binary tree

Problem statement- You have been given a Binary Tree of distinct integers and two nodes, ‘X’ and ‘Y.’ You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y.’

Let a tree t be a rooted tree with two nodes, X and Y. The Lowest common ancestor between these two nodes will be the lowest node in T, with both X and Y as descendants. The LCA of X and Y in T is the shared ancestor of X and Y located farthest from the root. Computing LCA is useful for determining the distance between pairs of nodes in a tree.

We can compute the distance from X to Y as the distance from the root to X, plus the distance from the root to Y, minus twice the distance from the root to their LCA.

Now we will see some methods to find LCA in the binary tree.

You can check this problem - LCA Of Binary Tree

Method 1 (By Storing root to X and root to Y paths)

This algorithm is of time complexity O(n) to find the LCA of X and Y.

Find and store the path from root to node X in an array or a vector.

Find and store the path from the root to node Y in another array or a vector.

Now traverse through both the arrays till the values are identical and return the common element of both arrays before the mismatch.

The implementation of the above algorithm is given below.

Code-

#include <iostream> #include <vector> using namespace std; struct Node { int key; struct Node *left, *right; }; Node * newNode(int k) { Node *temp = new Node; temp->key = k; temp->left = temp->right = NULL; return temp; } bool findPath(Node *root, vector<int> &path, int k) { if (root == NULL) return false; path.push_back(root->key); if (root->key == k) return true; if ( (root->left && findPath(root->left, path, k)) || (root->right && findPath(root->right, path, k)) ) return true; path.pop_back(); return false; } int findLCA(Node *root, int X, int Y) { vector<int> path1, path2; if ( !findPath(root, path1, X) || !findPath(root, path2, Y)) return -1; int i; for (i = 0; i < path1.size() && i < path2.size() ; i++) if (path1[i] != path2[i]) break; return path1[i-1]; } 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); cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6); cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4); cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4); return 0; }

Output-

Time complexity -

The time complexity of the above code to find the LCA of the binary tree is O(n). Traversal of the tree is done twice, and path arrays are compared.

Method 2 (Using Single Traversal)

If we assume that the keys X and Y are present in a binary tree, we can find the LCA of the tree by traversing the tree only once with extra storage of path arrays.

The point is to traverse the binary tree starting from the root.

If any of the keys X or Y matches with the root, then the root is the LCA of the binary tree. But if it doesn't match any of the given keys, we recure for the left and right subtree. When one key is present in the left subtree, and the other is in the right subtree, then the right subtree key is the LCA of the binary tree. But if both the keys are in the left subtree, then the left subtree also has LCA; otherwise, the right subtree has LCA.

The implementation of the above algorithm is given below.

Code-

#include <bits/stdc++.h> using namespace std; struct Node { struct Node *left, *right; int key; }; Node* newNode(int key) { Node *temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; } struct Node *findLCA(struct Node* root, int X, int Y) { if (root == NULL) return NULL; if (root->key == X || root->key == Y) return root; Node *left_lca = findLCA(root->left, X, Y); Node *right_lca = findLCA(root->right, X, Y); 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)->key; cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6)->key; cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4)->key; cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4)->key; return 0; }

Output-

Time complexity-

The time complexity of the above code to find the LCA of the binary tree is O(n), as the method does a simple binary tree traversal in a bottom-up fashion.