Given a binary tree and two nodes x and y in it, find lowest common ancestor (LCA) of x and y in it.

The lowest common ancestor (LCA) of two nodes x and y in a binary tree is the lowest (i.e. deepest) node that has both x and y as descendants, where each node can be descendant of itself (so if x is reachable from w,w is the LCA). In other words, the LCA of x and y is the shared ancestor of x and y that is located farthest from root.

For example, consider below binary tree. Let x = 6 and y = 7

The common ancestors of the nodes x and y are 1 and 3. Out of nodes 1 and 3, the LCA is 3 as it is farthest from the root.

Simple solution would be to store path from root to x and path from root to y in two auxiliary arrays. Then we traverse both arrays simultaneously till the values in the arrays match. The last matched value will be the LCA. If the end of one array is reached then last seen value is LCA. The time complexity of this solution is O(n) but auxiliary space used by it is O(n) required for storing two arrays.

We can recursively find lowest common ancestor of nodes x and y present in the binary tree. The trick is to find the node in binary tree which has one key present in its left subtree and the other key present in right subtree. If any such node is present in the tree, then it is LCA else if y lies in subtree rooted at node x, then x is the LCA else if x lies in subtree rooted at node y, then y is the LCA.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Helper function to check if given node is present in binary tree or not bool isNodePresent(Node* root, Node* node) { // base case if (root == nullptr) return false; // if node is found, return true if (root == node) return true; // return true if node is found in the left subtree or right subtree return isNodePresent(root->left, node) || isNodePresent(root->right, node); } // Function to find lowest common ancestor of given nodes x and y where // both x and y are present in the binary tree. // The function returns true if x or y is found in subtree rooted at root // lca -> stores LCA(x, y) and it is passed by reference to the function bool findLCA(Node* root, Node* &lca, Node* x, Node* y) { // base case 1: return false if tree is empty if (root == nullptr) return false; // base case 2: return true if either x or y is found if (root == x || root == y) { // set lca to current node lca = root; return true; } // recursively check if x or y exists in the left subtree bool left = findLCA(root->left, lca, x, y); // recursively check if x or y exists in the right subtree bool right = findLCA(root->right, lca, x, y); // if x is found in one subtree and y is found in other subtree, // update lca to current node if (left && right) lca = root; // return true if x or y is found in either left or right subtree return left || right; } // Function to find lowest common ancestor of nodes x and y void findLCA(Node* root, Node* x, Node* y) { // lca stores lowest common ancestor of x and y Node *lca = nullptr; // call LCA procedure only if both x and y are present in the tree if (isNodePresent(root, y) && isNodePresent(root, x)) findLCA(root, lca, x, y); // if LCA exists, print it if (lca != nullptr) cout << "LCA is " << lca->data << endl; else cout << "LCA do not exist\n"; } |

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

**References:**

https://en.wikipedia.org/wiki/Lowest_common_ancestor

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply