# Java not-so-short but Crystal Clear Solution (with a condensed version and explanations)

• My solution might not be the shortest, but hopefully easier to understand. I also included a condensed version from another post and will explain how my solution can be shortened into a more concise one.

My solution:
I used a bottom up approach. Use recursion to traverse the tree to bottom. If we haven't found any of p or q, return `null`. If we have found p or q in the subtree, return it. If we know p and q are in the left or right subtrees respectively, we have found the `lowest common ancestor`, and we return it all the way to the top. There are a total of 6 cases I considered (marked in code as comment).

1. TreeNode p and q are in left and right (or right and left) subtree, respectively. This problem assumes no duplication of TreeNode p or q, so the current root must be the lowest common ancestor.

2. Either p or q is found in either left or right subtree, and root is the other we are looking for.

3. We can't find both p and q, but current root is either p or q.

4. We can't find any new information about p or q, but the left subtree contains p or q. This can actually happen in two cases:
a) We have found one of p and q, but haven't found the other
b) We have found the lowest common ancestor of p and q, but p or q itself happens to be the lowest common ancestor.

5. Same as 4, no new information, but right subtree contains p or q.

6. None of the above conditions were met. This can be caused by:
a) We have found the lowest common ancestor (which may not be equal to p or q). One of `left` and `right` is the common ancestor, and the other is `null`.
b) We haven't found any of p and q yet (both `left` and `right` are `null`).
In this case, we can simply return the `non-null` TreeNode. If they are both `null`, return null. This can be shortened to one line.

Basically I draw a subtree that we meet during a recursive step and figured out the cases above.
x
/ \
yz

This problem also assumes that p and q must exist in the tree, not sure if my code works if existence is not guaranteed.

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return root;
// recursive calls
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// bottom-up backtracing
// 1
if ((left == p && right == q) || (left == q && right == p)) {
return root;
}
// 2
if ((left == p && root == q) || (left == q && root == p) || (right == p && root == q) || (right == q && root == p)) {
return root;
}
// 3
if (root == p || root == q) {
return root;
}
// 4
if (left == p || left == q) {
return left;
}
// 5
if (right == p || right == q) {
return right;
}
// 6
return left == null ? right : left;
}
}
``````

This amazong 10-line solution is taken from: https://discuss.leetcode.com/topic/18738/10-line-java-solution-solved-in-one-traversal
My solution is a bit complex, but assuming (I think) both p and q exists in the tree, it can be shortened to this concise one.

It also uses a bottom-up approach. Basically we recurse to traverse the tree. When we have found p or q, return it all the way till we find both p and q in separate subtrees, where the current root is the LCA. Then return it.

``````// condensed version
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}

TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);

if(root == p || root == q){
return root;
}

if(l != null && r != null){
return root;
}

return l != null ? l:r;
}
}
````````

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