# 4 lines C++/Java/Python/Ruby

• 1,2,3,null,null,4,5,8,9,7,6,4,5

That's not a valid binary tree.
According to your data, element 2's children is null and null which is fine, except that 2.left which is null, has children 8 and 9 and 2.right which is null has children 7 and 6. That's a broken tree.

• This 4 line solution is pretty but its not efficient. You always walk the entire tree.

Imagine if you're tree is enormous, but the first 2 elements are your match.
Also consider that you find both children on the left side of a really large tree, you still walk the entire right side before popping out.

My solution (which I'm not claiming to be the prettiest or most efficient)

``````// assumes a and b and ancestor are not null
// Time Complexity: O(n) Worst case we may have to touch every node
// Space Complexity: O(n) Worst case if very unbalanced tree. Typical would be O(Log(n)).
private static int findLCA(TreeNode root,
Integer a, Integer b, Ref<TreeNode> ancestor) {
if (root == null)
return 0;

int m = 0;
if (a.equals(root.val))
m++;
if (b.equals(root.val))
m++;

if (m != 2)
m += findLCA(root.left, a, b, ancestor);
if (m != 2)
m += findLCA(root.right, a, b, ancestor);

if (m == 2)
if (ancestor.val == null)
ancestor.val = root;

return m;
}``````

• @aaron65 That's not a solution. There's at least something missing.

• Why would it let 'left != null && right != null' happen?

• @StefanPochmann, regarding your java solution.
if q is descendant of p, then lowestCommonAncestor() returns immediately, if root is p.
So q will be never found, right?

• @xibodoh Won't be found explicitly, yes.

• @StefanPochmann What if tree contains p and it does not contain q ?

• Hi @StefanPochmann
The above solution won't work for this:
`[37,-34,-48,null,-100,-100,48,null,null,null,null,-54,null,-71,-22,null,null,null,8]`
and 2 nodes are passed this way:
`root.left.right` -100
`root.right.right` 48

Solution should be -48, code prints 37
Surprisingly this passes leetcode tests.

Thanks.

• @elbek.kamol Huh? 37 is correct for that.

• @StefanPochmann
here is the tree:

the result is shown in circle.

Thanks.

• @elbek.kamol You're looking at the wrong -100. You said "root.left.right -100", not "root.right.left -100".

• This post is deleted!

• The question doesn't mention whether it has duplicates if you have a example, like
p = 1 q = 2
---3
--/ -\
-1---4
---- /- \
--- 1---2

Your algorithm will return node 3 as the result, but actually the answer is node 4, please correct me if I am wrong

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