## Lowest Common Ancestor of Binary Tree

Difficulty: Medium

Asked in: Amazon, Facebook, Adobe

**Understanding The Problem**

**Problem Description**

Given a binary tree, write a program to find the **lowest common ancestor (LCA)** of two given nodes in the tree.

**Problem Note**

**Lowest Common ancestor:**The lowest common ancestor is defined between two nodes node1 and node2 as the lowest node in a tree that has both node1 and node2 as descendants (a node can be a descendant of itself).- All of the node’s values will be unique.
- node1 and node2 are different and both values will exist in the binary tree.
- You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.

**Example 1**

**Example 2**

The node structure passed to your function will be

```
class TreeNode
{
int data
TreeNode left
TreeNode right
}
```

#### Solutions

We will be discussing recursive and iterative approaches

**Recursive approach**— Recursively look for any of the two nodes and return it, the first node to encounter both of them in its subtree is the ancestor.**Iterative approach**— Follow the recursive procedure by using a stack and a parent map for each node.

#### 1. Recursive Approach

A pretty intuitive approach is to traverse the tree in a depth-first manner. The moment you encounter either of the nodes `node1`

or `node2`

, return the node. The least common ancestor would then be the node for which both the subtree recursions return a non-NULL node. It can also be the node which itself is one of `node1`

or `node2`

and for which one of the subtree recursions returns that particular node.

Solution steps

- Start traversing the tree from the root node.
- If the current node itself is one of
`node1`

or`node2`

, we would return that node. - If the left or the right subtree returns a non-NULL node, this means one of the two nodes was found below.
- If at any point in the traversal, both the left and right subtree return some node, this means we have found the lowest common ancestor for the nodes
`node1`

and`node2`

.

Pseudo Code

```
TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
if(not root)
return NULL
if (root == node1 or root == node2)
return root
TreeNode left = lowestCommonAncestor(root.left, node1, node2)
TreeNode right = lowestCommonAncestor(root.right, node1, node2)
if(not left)
return right
else if(not right)
return left
else
return root
}
```

Complexity Analysis

**Time Complexity**: O(n), where n is the total number of nodes in the tree.

**Space Complexity**: O(n)

Critical ideas to think

- How will this algorithm work if the lowest common ancestor of node2 is an ancestor of node1?
- Can you think of a case when the worst-case space complexity is O(n)?
- How does this algorithm work if any of the two nodes fail to exist in the tree?

#### 2. Iterative Approach

An intuition for an iterative approach is if we have parent pointers for each node we can traverse back from `node1`

and `node2`

to get their ancestors. The first common node we get during this traversal would be the LCA node. So, We can save the parent pointers in a dictionary as we traverse the tree.

Solution step

- Start from the root node and traverse the tree.
- Until we find
`node1`

and`node2`

both, keep storing the parent pointers in a dictionary. - Once we have found both
`node1`

and`node2`

, we get all the ancestors for`node1`

using the parent dictionary and add to a set called`ancestors`

. - Similarly, we traverse through ancestors for node
`node2`

. If the ancestor is present in the ancestors set for`node1`

, this means this is the first ancestor common between`node1`

and`node2`

(while traversing upwards) and hence this is the LCA node.

Pseudo Code

```
TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
// create a parent map that maps the childnode with its parent
map parent({{root,NULL}})
// a stack to make a post order traversal iteratively
stack stk({root})
while(not node1 exist in parent or not node2 exist in parent){
TreeNode n = stk.top()
stk.pop()
if(n.left) {
parent[n.left] = n
stk.push(n.left)
}
if(n.right) {
parent[n.right] = n
stk.push(n.right)
}
}
// ancestor set for node1
set path
while(node1 is not NULL) {
path.insert(node1)
node1 = parent[node1]
}
// The first ancestor of node2 which appears in
// node1's ancestor set is their lowest common ancestor.
while(node2 not exist in path)
node2 = parent[node2]
return node2
}
```

Complexity Analysis

**Time Complexity:** O(n)

**Space complexity**: O(n). In the worst-case space utilized by the stack, the parent pointer dictionary and the ancestor set would be `n`

each, since the height of a skewed binary tree, could be `n`

.

Critical Ideas to Think

- Which traversal technique we are using for traversal in the tree for this algorithm?
- Why did we maintain a hash map?
- What if one of the nodes is itself the LCA?
- What exactly does the path set represents in the pseudo code?
- Can you think of an iterative approach without using hashmap or storing parent pointer?

#### Comparison of solutions

#### Suggested problems to solve

- Find the intersection point of two singly linked lists
- Find the LCA of a binary search tree
- Find LCA of any number of nodes in a Binary Tree
- Kth ancestor of a node in a binary tree
- Kth ancestor of a node in N-ary tree

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**Happy Coding! Enjoy Algorithms!**