Least common ancestor in binary tree

This code finds a common ancestor. If one of the input does not exist in the tree then throws an exception. This does not use extra storage. It does not even traverse more than what it should be. It would also account for duplicate node values in binary tree.

I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

```
public class LeastCommonAncestor {

private TreeNode root;

private static class TreeNode {
TreeNode left;
TreeNode right;
int item;

TreeNode (TreeNode left, TreeNode right, int item) {
this.left = left;
this.right = right;
this.item = item;
}
}

public void createBinaryTree (Integer[] arr) {
if (arr == null) {
throw new NullPointerException("The input array is null.");
}

root = new TreeNode(null, null, arr[0]);

final Queue queue = new LinkedList();
queue.add(root);

final int half = arr.length / 2;

for (int i = 0; i ());

if (lcaData.lca != null) {
return lcaData.lca.item;
} else {

throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
}
}

private boolean foundMatchAndDuplicate (TreeNode node, LCAData lcaData, int n1, int n2, Set set) {
if (node == null) {
return false;
}

// when both were found
if (lcaData.count == 2) {
return false;
}

// when only one of them is found
if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
if (!set.contains(node.item)) {
lcaData.count++;
return true;
}
}

boolean foundInCurrent = false;
// when nothing was found (count == 0), or a duplicate was found (count == 1)
if (node.item == n1 || node.item == n2) {
if (!set

There are a number of issues in your code that I can see:

-
Input validation.

public void createBinaryTree (Integer[] arr) {
    if (arr == null)  {
        throw new NullPointerException("The input array is null.");
    }

    root = new TreeNode(null, null, arr[0]);

You check the arr is not null, but you do not check that its arr.length > 0. An empty array will cause an ArrayIndexOutOfBounds exception.

-
AutoBoxing

You have the method:

public void createBinaryTree (Integer[] arr) { ... }

which takes an array of Integer[], which you then have to check for nulls in, and then you store the values away as:

current.left = new TreeNode(null, null, arr[left]);

where the constructor for TreeNode is an int value.

Why do you take an Integer[] array at all? it should all be int[]...

As a consequence, you have null-value issues in your code which make your code harder to read.

-
The inner iteration of your code is unnecessarily complicated. This code here:

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

should not start with i = 0 because arr[0] was already included as the root. This is not obvious. You should have code that looks more like (note the + 1 and + 2 have been changed to ` and + 1 respectively):

// start at 1 because arr[0] is already processed.
    for (int i = 1; i < half; i++) {
        if (arr[i] != null) {
            final TreeNode current = queue.poll();
            final int left = 2 * i;
            final int right = 2 * i + 1;

-
In your recursion method, set is a really, really bad variable name, it should be dupcheck or something.

-
BUG your code does not find the least common ancestor (for whatever definition of Least you choose). This code here:

boolean foundInLeft = foundMatchAndDuplicate(node.left, lcaData, n1, n2, set);
boolean foundInRight = foundMatchAndDuplicate(node.right, lcaData, n1, n2, set);

means that if there is a (duplicate) match in both the left, and the right, that whatever happened in the 'left' side is kept, and whatever happens in the right side is 'forgotten' (because you later have the check && lcaData.lca == null` ). As a result, you only identify the 'left-most' common ancestor.

StackExchange Code Review Q#31331, answer score: 6