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));
}