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

## Problem Statement

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

**Examples**

### Confused about your next job?

## Recursive Approach

The idea is to traverse the **binary tree** in a **depth-first **approach and search for both nodes in the binary tree. The LCA of both nodes is the node, for which the recursion on the 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 Implementation

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 Implementation

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 Implementation

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 appears for both nodes, return that node, since it is the
**LCA**of both nodes. - Else, continue traversing.

### C++ Code 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 Code 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 Code 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

## FAQs

### Q.1: What will happen if the tree is a BST?

**Ans: **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.

### Q.2: Why is a Hashmap used?

**Ans:** 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.