## Find the 1st common ancestor of two nodes in a binary tree

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. NOTE: This is not necessarily a binary search tree.

My initial thoughts:
Consider two nodes u and v, together with a root node. There are several cases we need to consider:

1. u is the ancestor of v. then return u.
2. v is the ancestor of u. then return v.
3. left subtree of root contains u and right subtree of root contains v. then return root.
4. left subtree of root contains v and right subtree of root contains u. then return root.

My initial codes:

```	public static BinaryTreeNode<Integer> FCA(BinaryTreeNode<Integer> root,
BinaryTreeNode<Integer> u, BinaryTreeNode<Integer> v) {
boolean uInLeft = contain(root.getLeft(), u);
boolean uInRight = contain(root.getRight(), u);
boolean vInLeft = contain(root.getLeft(), v);
boolean vInRight = contain(root.getRight(), v);

if (!uInLeft && !uInRight && !vInLeft && !vInRight)
return null;

if (uInLeft && vInRight)
return root;
else if (vInLeft && uInRight)
return root;
else if (root == u && (vInLeft || vInRight))
return root;
else if (root == v && (uInLeft || uInRight))
return root;
else {
BinaryTreeNode<Integer> leftAncestor = FCA(root.getLeft(), u, v);
BinaryTreeNode<Integer> rightAncestor = FCA(root.getRight(), u, v);
if (leftAncestor == null && rightAncestor != null)
return rightAncestor;
else if (leftAncestor != null && rightAncestor == null)
return leftAncestor;
else
return null;
}

}

public static boolean contain(BinaryTreeNode<Integer> root,
BinaryTreeNode<Integer> node) {
if (root == node)
return true;
else if (root == null)
return false;
else
return contain(root.getLeft(), node)
|| contain(root.getRight(), node);
}

Solution:
public static BinaryTreeNode<Integer> commonAncestor(
BinaryTreeNode<Integer> root, BinaryTreeNode<Integer> u,
BinaryTreeNode<Integer> v) {
if (contain(root.getLeft(), u) && contain(root.getLeft(), v))
return commonAncestor(root.getLeft(), u, v);
if (contain(root.getRight(), u) && contain(root.getRight(), v))
return commonAncestor(root.getRight(), u, v);
return root;
}

Comments: The solution simplifies mine by combing cases.There are actually two simple cases: u and v are along the same side v.s. u and v are on different sides.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b27fe64f003d', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b27fe64f006b',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b27fe64f006e',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});