# First Common Ancestor

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.

Could you solve it in a simple way first, knowing that each node has a link to its parent?

How about if there is no link to its parent?

NOTE: This is not necessarily a binary search tree.

## Link here to the repo to solve the problem

๐## ๐ Tips

The first common ancestor is the deepest node such that p and q are both descendants. Think about how you might identify this node.

How would you figure out if p is a descendent of a node n?

Start with the root. Can you identify if root is the first common ancestor? If it is not, can you identify which side of root the first common ancestor is on?

Try a recursive approach. Check if p and q are descendants of the left subtree and the right subtree. If they are descendants of different subtrees, then the current node is the first common ancestor. If they are descendants of the same subtree, then that subtree holds the first common ancestor. Now, how do you implement this efficiently?

In the more naive algorithm, we had one method that indicated if x is a descendent of n, and another method that would recurse to find the first common ancestor. This is repeatedly searching the same elements in a subtree. We should merge this into one firstCommonAncestor function. What return values would give us the information we need?

The firstCommonAncestor function could return the first common ancestor (if p and q are both contained in the tree), p if P is in the tree and not q, q if q is in the tree and not p, and null otherwise.

Careful! Does your algorithm handle the case where only one node exists? What will happen? You might need to tweak the return values a bit.

## ๐ Solution 1

The simplest of solutions if we could use data structures, would be to just add the trace of nodes, all the way to the root. Finding the first node which intersects both paths.

```
public BinaryTreeNode solution(BinaryTreeNode p, BinaryTreeNode q) {
ArrayList<BinaryTreeNode> pList = new ArrayList<>();
ArrayList<BinaryTreeNode> qList = new ArrayList<>();
while (p.parent != null) {
p = p.parent;
pList.add(p);
}
while (q.parent != null) {
q = q.parent;
qList.add(q);
}
for (BinaryTreeNode binaryTreeNode : pList) {
if (qList.contains(binaryTreeNode)) return binaryTreeNode;
}
return null;
}
```

But lets make this interesting, what about if we can't use any data structures?

## ๐ Solution 2

In case of not being able to store anything and if we know that the nodes link to the parent we could solve the problem like this:

First we get the depth of both nodes, the difference between these two will tell us how much we need to move the lowest one up. Once we know that we can move each of them up until we found the common ancestor, if no ancestor is found we just return null.

This approach would take O(D), where D is the depth of the tree.

```
public BinaryTreeNode solution(BinaryTreeNode p, BinaryTreeNode q) {
int difference = depth(p) - depth(q);
BinaryTreeNode first = difference > 0 ? p : q; // lowest depth
BinaryTreeNode second = difference < 0 ? p : q;
first = moveUp(first, difference);
while (first != second && first.parent != null & second.parent != null) {
first = first.parent;
second = second.parent;
}
return first == null || second == null ? null : first;
}
private BinaryTreeNode moveUp(BinaryTreeNode node, int difference) {
while (difference != 0) {
node = node.parent;
difference--;
}
return node;
}
private int depth(BinaryTreeNode n) {
int c = 0;
while (n.parent != null) {
c++;
n = n.parent;
}
return c;
}
```

## ๐ Solution 3

A solution in case our nodes did not have a link to the parents would be to traverse from the root down.

In this solution I use two utility functions, "covers" will iterate through both sides of the tree, and perform a check until it finds the node is looking for.

The helper function will check on which side the nodes are, if they are on different sides - it can assume that node is the common ancestor, otherwise it needs to keep going deeper.

```
public BinaryTreeNode noLinkToParentSolution(BinaryTreeNode root, BinaryTreeNode p, BinaryTreeNode q) {
// check if node is not in the tree
if (!covers(root, p) || !covers(root, q)) {
return null;
}
return ancestorHelper(root, p, q);
}
private BinaryTreeNode ancestorHelper(BinaryTreeNode root, BinaryTreeNode p, BinaryTreeNode q) {
if (root == null || p == null || q == null) return root;
boolean pIsOnLeft = covers(root.left, p);
boolean qIsOnLeft = covers(root.left, q);
if (pIsOnLeft != qIsOnLeft) return root; // nodes are on different sides, so common ancestor must be this node
BinaryTreeNode childSide = pIsOnLeft ? root.left : root.right;
return ancestorHelper(childSide, p, q);
}
private boolean covers(BinaryTreeNode root, BinaryTreeNode n) {
if (root == null) return false;
if (root == n) return true;
return covers(root.left, n) || covers(root.right, n);
}
```

*Question borrowed from โCracking the coding interviewโ*