Lowest Common Ancestor

Problem Statement

Given a binary tree of integers. The task is to find the Lowest Common Ancestor of two nodes in the given tree.

The Lowest Common Ancestor of two nodes is the lowest node that has both the nodes as descendants.

Examples

Recursive Approach

The idea is to traverse the binary tree in a depth-first approach and search for both the nodes in the binary tree. The LCA of both the nodes is the node, for which the recursion on subtree returns the same node.

Algorithm

• Start from the DFS from the root of the binary tree.
• Recurse the left and right subtree.
• If the current nodes visited is any of the given nodes whose LCA is to be found, return that node.
• Else, for both the nodes, if the subtree provides the same non NULL node, it is the LCA, hence return the node.

C++ Code For Recursive Approach

struct Node * findLCA(struct Node * root, int n1, int n2) {
  if (root == NULL) return NULL;
  if (root -> key == n1 || root -> key == 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;
}

Java Code For Recursive Approach

Node root;
 
Node findLCA(int n1, int n2) {
  return findLCA(root, n1, n2);
}
Node findLCA(Node node, int n1, int n2) {
  if (node == null)
    return null;
 
  if (node.data == n1 || node.data == n2)
    return node;
 
  Node left_lca = findLCA(node.left, n1, n2);
  Node right_lca = findLCA(node.right, n1, n2);
 
  if (left_lca != null && right_lca != null)
    return node;
 
  return (left_lca != null) ? left_lca : right_lca;
}

Python Code For Recursive Approach

def findLCA(root, n1, n2):
 
    if root is None:
        return None
 
    if root.key == n1 or root.key == n2:
        return root
 
    left_lca = findLCA(root.left, n1, n2)
    right_lca = findLCA(root.right, n1, n2)
 
    if left_lca and right_lca:
        return root
 
    return left_lca if left_lca is not None else right_lca

Time Complexity:O(N) where N is the number of nodes of the binary tree.
Space Complexity:O(N), because of the recursive stack

Approach 2 (Iterative)

The iterative approach to solve this problem is to use parent pointers. The idea is to establish parent pointers for each node so that we can traverse back from the nodes to get their descendants.

Algorithm

• Start traversing from the root node.
• For each node visited, keep storing the parent pointers in a map.
• Continue, until both the given nodes are found.
• Since, all parent points for each node are stored now, traverse back for node1. Similarly, for node2, traverse back through the parent pointers.
• If at any point, the same ancestor appear for both the nodes, return that node, since it is the LCA of both nodes.
• Else, continue traversing.

C++ Implementation

Node * LCA(Node * n1, Node * n2) {
  map < Node * , bool > ancestors;
  while (n1 != NULL) {
    ancestors[n1] = true;
    n1 = n1 -> parent;
  }
  while (n2 != NULL) {
    if (ancestors.find(n2) != ancestors.end())
      return n2;
    n2 = n2 -> parent;
  }
 
  return NULL;
}

Java Implementation

Node LCA(Node n1, Node n2) {
  Map < Node, Boolean > ancestors = new HashMap < Node, Boolean > ();
  while (n1 != null) {
    ancestors.put(n1, Boolean.TRUE);
    n1 = n1.parent;
  }
  while (n2 != null) {
    if (ancestors.containsKey(n2) != ancestors.isEmpty())
      return n2;
    n2 = n2.parent;
  }
 
  return null;
}

Python Implementation

def find_lca(n1, n2):
    seen_on_path: Set[BinaryTreeNode] = set()
 
    while n1 or n2:
 
        if n1:
            if n1 in seen_on_path:
                return n1
            seen_on_path.add(n1)
            n1 = n1.parent
 
        if n2:
            if n2 in seen_on_path:
                return n2
            seen_on_path.add(n2)
            n2 = n2.parent
    return None

Time Complexity:O(N) where N is the number of nodes of the binary tree.
Space Complexity:O(N), as a map is used.

Practice Question

Least Common Ancestor

FAQs

What will happen if the tree is a BST?
Though the time complexity will remain the same, for BST, fewer checks need to be done, as we know can apply the property of BST.

Why is a hashmap used?
The hashmap is used to store the parent pointers of all the nodes so that the nodes can be traversed back and the common ancestors can be found.