4
\$\begingroup\$

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));
       }
    }
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.