Find Least Common Ancestor (LCA) of binary tree

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
         /  \
	/    \
       10     20
      / \     / \
     /   \   /   \
    8    12 16   25

LCA(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
         /  \
	/    \
       10     20
      / \     / \
     /   \   /   \
    8    12 16   25

LCA(10, 25) = 15

Time complexity: O(n).
Space complexity: O(1).