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

### Example

Input: 8 / \ / \ 4 10 / \ / \ / \ / \ 2 6 9 12 Output: lca(2, 6) = 4; lca(2, 12) = 8; lca(4, 9) = 8; lca(6, 9) = 8; lca(9, 12) = 10;

One simple solution is to find all the nodes from x to y and store them in two different arrays and then iterate both the arrays and check for the common value and return the last one. It will take O(n) time and O(n) space.

We can optimize it further and solve it without using any extra space with the below solution.

## Recursive solution: LCA of a binary search tree.

Conceptually this is how it works.

- We just need to find if there exists a node in the tree which is less than (or equal) than any of the given nodes and greater than (or equal) than any of the given nodes. If it exits then it is the least common ancestor (LCA).
- For this, traverse the tree and check if the current is less than any of the given nodes, then recur and check in the right subtree, else if it is greater than given nodes then check if left subtree.
- If exits, then return the node value, else return null.

For this solution we will need a helper function to cross check if the given nodes exists in the tree and only when they exists, we will look for the LCA.

//Search in tree const search = (root, key) => { //traverse the tree and search for the key while(root !== null){ //If the current node is greater than the key then go to the left subtree, //else go to the right subtree if(key < root.val){ root = root.left; }else if(key > root.val){ root = root.right; }else{ //if key is found return true return true; } } //if key is not found return false return false; } //Recursive function find the lowest common ancestor of given nodes, //where both nodes x, y is present in the tree const findLCARecursive = (root, x, y) => { //base case if(root === null){ return null; } //if both x and y is smaller than root, LCA can be found in left subtree if(root.val > Math.max(x, y)){ return findLCARecursive(root.left, x, y); } //if both x and y is greater than root, LCA can be found in right subtree else if(root.val < Math.min(x, y)){ return findLCARecursive(root.right, x, y); } //else if one key is less (or equal) and other key is //greater (or equal) then current node is LCA of both return root.val; } //Check and get the LCA const LCA = (root, x, y) => { //return if tree is empty or any of the nodes is not present if(root === true || !search(root, x) || !search(root, y)){ return null; } //find the LCA if nodes are present return findLCARecursive(root, x, y); }

Input: const tree = new Node(15); tree.left = new Node(10); tree.right = new Node(20); tree.left.left = new Node(8); tree.left.right = new Node(12); tree.right.left = new Node(16); tree.right.right = new Node(25); console.log(LCA(tree, 10, 25)); Output:15/ \ / \1020 / \ / \ / \ / \ 8 12 1625LCA(10, 25) = 15

Time complexity: O(n).

Space complexity: O(n) if call stack is considered, else O(1).

## Iterative solution: Least common ancestor of a binary search tree

The recursive solution can be converted to a iterative one, we just have to move to the right sub-tree in each iteration.

//Search the tree const search = (root, key) => { //traverse the tree and search for the key while(root !== null){ //If the current node is greater than the key then go to the left subtree, //else go to the right subtree if(key < root.val){ root = root.left; }else if(key > root.val){ root = root.right; }else{ //if key is found return true return true; } } //if key is not found return false return false; } //Iterative solution const findLCAIterative = (root, x, y) => { //return if tree is empty or any of the both nodes are empty if(root === true || !search(root, x) || !search(root, y)){ return null; } //start from root let curr = root; //traverse the tree while(curr !== null){ //if both x & y are less than current node, then LCA exists in left subtree if(curr.val > Math.max(x, y)){ curr = curr.left; } //if both x & y are greater than current node, then LCA exists in right subtree else if (curr.val < Math.min(x, y)){ curr = curr.right; } //if one key is greater (or equal) than node and one key is //smaller (or equal) than node, then the current node is LCA else{ return curr.val; } } //If LCA is not found then return null; return curr; }

Input: const tree = new Node(15); tree.left = new Node(10); tree.right = new Node(20); tree.left.left = new Node(8); tree.left.right = new Node(12); tree.right.left = new Node(16); tree.right.right = new Node(25); console.log(findLCAIterative(tree, 10, 25)); Output:15/ \ / \1020 / \ / \ / \ / \ 8 12 1625LCA(10, 25) = 15

Time complexity: O(n).

Space complexity: O(1).