# Least common ancestor (LCA) in a binary tree

Find the LCA in binary tree, where a node is also its own ancestor.

This question is attributed to GeeksForGeeks. I'm looking for code review, optimizations and best practices.

public class LeastCommonAncestor {

private TreeNode root;

/**
* Constructs a binary tree in order of elements in an array.
* After the number of nodes in the level have maxed, the next
* element in the array would be a child of leftmost node.
*/
public LeastCommonAncestor(List<Integer> items) {
createBinaryTree(items);
}

private static class TreeNode {
TreeNode left;
TreeNode right;
int item;
public TreeNode(int item) {
this.item = item;
}
}

public void createBinaryTree(List<Integer> items) {
if (items.size() == 0)  {
throw new IllegalArgumentException("The input array is null.");
}

root = new TreeNode(items.get(0));

final Queue<TreeNode> queue = new LinkedList<TreeNode>();

final int half = items.size() / 2;

for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;

if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(right));
}
}
}
}

/**
* Returns the lease common ancestor of items. A item is also an ancestor or itself. If item1 is parent of item2 or
* item1 == item2, then item1 is the value returned. If tree contains duplicate elements then the ancestor
* encountered in the inorder first in the preorder traversal is the one which is returned.
*
*
* @param item1     The first item.
* @param item2     The second item.
* @return          The common ancestor of item1 and item2.
*/
public Integer getLeastCommonAncestor(int item1, int item2) {
final List<Integer> item1Path = new ArrayList<>();
final List<Integer> item2Path = new ArrayList<>();

if (!populatePath(root, item1Path, item1)) {
throw new IllegalArgumentException("The item1: " + item1 + " is not a tree node.");
}

if (!populatePath(root, item2Path, item2)) {
throw new IllegalArgumentException("The item1: " + item2 + " is not a tree node.");
}

return fetchLeastCommonAncestor(item1Path, item2Path);
}

private boolean populatePath(TreeNode node, List<Integer> items, int item) {
if (node == null) {
return false;
}

if (node.item == item) {
return true;
}

if (populatePath(node.left, items, item) || populatePath(node.right, items, item)) {
return true;
}

items.remove(items.size() - 1);
return false;
}

private static int fetchLeastCommonAncestor(List<Integer> item1Path, List<Integer> item2Path) {
int minLength = Math.min(item1Path.size(), item2Path.size());
int i;

for (i = 0; i < minLength; i++) {
if (item1Path.get(i) != item2Path.get(i)) {
break;
}
}
return item1Path.get(i - 1);
}
}

public class LeastCommonAncestorTest {

@Test
public void testItem1AndItem2Unique() {
LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
assertEquals(1, (int)lcs.getLeastCommonAncestor(4, 6));
}

@Test
public void testItem1ParentOfItem2() {
LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
assertEquals(2, (int)lcs.getLeastCommonAncestor(2, 4));
}

@Test
public void testItem1SameAsItem2() {
LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
assertEquals(2, (int)lcs.getLeastCommonAncestor(2, 2));
}

@Test
public void testItem1SameAsItem2SameAsRoot() {
LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
assertEquals(1, (int)lcs.getLeastCommonAncestor(1, 1));
}
}


Your createBinaryTree method is entirely procedural and the TreeNode class isn't much more than a data object. Also many of the checks in createBinaryTree are redundant. I also added 2 tests to consider edge conditions.

By moving more logic to the TreeNode class it can be tested separately from the rest of the program. I leave those tests as an exercise for the user.

the iteration over the list and having a Queue is a bit of duplication can be eliminated with some more thought.

There are more improvement to be made in the ancestor search. That is also procedural code

class TreeNode {
TreeNode left;
TreeNode right;
int item;
public TreeNode(int item) {
this.item = item;
}
{
left = new TreeNode(children.get(0));

if (children.size() > 1)
{
right = new TreeNode(children.get(1));
return Arrays.asList(left, right);
}
return Arrays.asList(left);
}
}

public void createBinaryTree(List<Integer> items)
{
if (items.size() == 0)
{
throw new IllegalArgumentException("The input array is null.");
}

root = new TreeNode(items.get(0));

final Queue<TreeNode> queue = new LinkedList<TreeNode>();

final int half = items.size() / 2;

for (int i = 0; i < half; i++)
{
final TreeNode current = queue.poll();

// right is not necessary when you build the children list
// final int right = 2 * i + 2;

// the math and magic numbers will confuse the next reader of the code
List<Integer> children = items.subList(calculateFirstChildIndex(i), items.size());

}
}

protected int calculateFirstChildIndex(int i)
{
return 2 * i + 1;
}


and in the test class

@Test
public void testOneItem()
{
LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1));
assertEquals(1, (int) lcs.getLeastCommonAncestor(1, 1));
}

@Test
public void testTwoItem()
{
LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2));
assertEquals(1, (int) lcs.getLeastCommonAncestor(1, 2));
}