# Given two nodes of a tree, return the deepest common ancestor of those nodes.

• Find deepest common ancestor of 2 nodes when root node is not known.

``````public interface FirstCommonAncestor {
class Node {
final Node parent;
final Node left;
final Node right;

public Node(Node parent, Node left, Node right) {
this.parent = parent;
this.left = left;
this.right = right;
}
boolean isRoot() {
return parent == null;
}

//     IMPLEMENT THIS FUNCTION
Node commonAncestor(Node one, Node two);
}
``````

Example:

``````    /**
* Given two nodes of a tree,
* method should return the deepest common ancestor of those nodes.
*
*          A
*         / \
*        B   C
*       / \
*      D   E
*         / \
*        G   F
*
*  commonAncestor(D, F) = B
*  commonAncestor(C, G) = A
*  commonAncestor(E, B) = B
*/
}
``````

• @mayuririmjha Please format your code properly by enclosing them with 3 backquotes.

`````````
`````````

• @mayuririmjha is deepest common ancestor the same like lowest common ancestor?

``````def lowestCommonAncestor(root,node1,node2):
if root == None:
return None
if root.val == node1.val or root.val == node2.val:
return root
l = lowestCommonAncestor(root.left,node1,node2)
r = lowestCommonAncestor(root.right,node1,node2)
if (l != None) and (r != None):
return root
elif l != None:
return root.left
else:
return root.right``````

• @elmirap Yes deepest common ancestor is same as LCA. However, you are not given access to root node. You have to implement following function which doesn't have root access:
Node commonAncestor(Node one, Node two);

• @mayuririmjha now I understand. Could you change the problem describtion you gave?Thank you!

• @elmirap Done!

• This post is deleted!

• Now it's just Intersection of Two Linked Lists, right?

• @StefanPochmann no, apart from next pointer Node class has parent pointer. Please check Node class above.

• @mayuririmjha exactly what StefanPochmann meant, you have to find the first node where two lists intersect.

``````def lowestCommonAncestor2(t1, t2):
while t1.parent != None and t1.parent != None:
if t1.parent == t2:
return t2
elif t2.parent == t1:
return t1
elif t1.parent == t2.parent:
return t1.parent
t1  = t1.parent
t2  = t2.parent
if t1.parent == None:
return t1
else:
return t2``````

• @mayuririmjha said in Given two nodes of a tree, return the deepest common ancestor of those nodes.:

apart from next pointer Node class has parent pointer

Um, it doesn't have `next`, and `parent` is of course playing the role of `next` in the analogy.

• @elmirap That doesn't really work.

• @StefanPochmann I will test, I wrote it for a few minutes, no tests

• Oh, I just realized it's maybe a slightly easier version of the linked list intersection problem, since here we know that there is an intersection. So testing with the old problem isn't 100% appropriate.

• @StefanPochmann I made tests with example tree and it is working ( I assume that t1 and t1 are different from None)
I will continue to test

• t1.parent != None and t1.parent != None

t1 and t1 are different from None

At least you're consistent :-P

(I hope you do see that bug now?)

• This post is deleted!

• om, I will check

• @elmirap No, I mean that you should test t1 and t2, not t1 and t1.

• @StefanPochmann I cannot imagine so silly bug.Thank you

``````while t1.parent != None and t2.parent != None:
if t1.parent == t2:
return t2
elif t2.parent == t1:
return t1
elif t1.parent == t2.parent:
return t1.parent
t1  = t1.parent
t2  = t2.parent
if t1.parent == None:
return t1
else:
return t2``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.