Least common ancestor (LCA) in a binary tree

Question

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>();
 queue.add(root);
 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));
 queue.add(current.left);
 }
 if (right < items.size() && items.get(right) != null) {
 current.right = new TreeNode(items.get(right));
 queue.add(current.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;
 }
 items.add(node.item);
 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));
 }
 }

Answer 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;
}
public List<TreeNode> addChildren( List<Integer> children)
{
 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>();
 queue.add(root);
 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());
 List<TreeNode> childNodes = current.addChildren(children);
 queue.addAll(childNodes);
 }
}
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));
}