3
\$\begingroup\$

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<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        final int half = arr.length / 2;

        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;

                if (arr[left] != null) {
                    current.left = new TreeNode(null, null, arr[left]);
                    queue.add(current.left);
                }
                if (right < arr.length && arr[right] != null) {
                    current.right = new TreeNode(null, null, arr[right]);
                    queue.add(current.right);
                }
            }
        }
    }

    private static class LCAData {
        TreeNode lca;
        int count;

        public LCAData(TreeNode parent, int count) {
            this.lca = parent;
            this.count = count;
        }
    }


    public int leastCommonAncestor(int n1, int n2) {
        if (root == null) {
            throw new NoSuchElementException("The tree is empty.");
        }

        LCAData lcaData = new LCAData(null, 0);

        foundMatchAndDuplicate (root, lcaData, n1,  n2, new HashSet<Integer>());

        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<Integer> 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.contains(node.item)) {
                set.add(node.item);
                lcaData.count++;
            }
            foundInCurrent = true;
        }

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

        if (((foundInLeft && foundInRight) || 
                (foundInCurrent && foundInRight) || 
                    (foundInCurrent && foundInLeft)) &&
                        lcaData.lca == null) {
            lcaData.lca = node;
            return true; 
        }
        return foundInCurrent || (foundInLeft || foundInRight);
    }

}
\$\endgroup\$

2 Answers 2

Reset to default
6
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

  1. With better API design you could avoid this condition completely:

    public int leastCommonAncestor(int n1, int n2) {
    if (root == null) {
        throw new NoSuchElementException("The tree is empty.");
    }
    ...
}

    I'd create a BinaryTree class which gets the input array in the constructor:

    public class BinaryTree {

    public BinaryTree(int[] input) {
        ...
    }

    public int getLeastCommonAncestor(int n1, int n2) {
        ...
    }
}

    If a client haven't constructed the object they are unable to call getLeastCommonAncestor() method.

    (Clean Code by Robert C. Martin, G31: Hidden Temporal Couplings, p302) 

  2. TreeNode(TreeNode left, TreeNode right, int item) {
    ...
}

    The first two parameters are unnecessary, the code always call the constructor with null values.

  3. The same issue here with the first parameer:

    public LCAData(TreeNode parent, int count) {
    ...
}

  4. If the input array contains a null it skips that branch. I'd throw an exception instead. I guess it's rather a bug on the side of the caller and there is not point to continue the calculation with wrong input. (The Pragmatic Programmer: From Journeyman to Master by Andrew Hunt and David Thomas: Dead Programs Tell No Lies.)

  5. It's not clear what are n1 and n2 here:

    public int leastCommonAncestor(int n1, int n2) {
    ...
}

    Are they values (TreeNode.item)? Are they indexes? Give them a more descriptive name.

  6. private boolean foundMatchAndDuplicate (TreeNode node, 
    LCAData lcaData, int n1, int n2, Set<Integer> set) {
    ...
}

    What's the purpose of the set here? A better name would help readers a lot.

  7. if (lcaData.lca != null) {
    return lcaData.lca.item;
} else {
    throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
}

    I'd invert this condition and remove the else block, it's easier to read:

    if (lcaData.lca == null) {
    throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
}
return lcaData.lca.item;

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

    It would help debugging if exception message contains the input values.

  9. I agree with @rolfl that you shouldn't use Integer[]. ;) Instead of it use generics and your call could be used with any type of objects! Here is almost the same code (mostly without the suggestions above) but with generics:

    public class LeastCommonAncestor<T> {
    private TreeNode<T> root;

    private static class TreeNode<T> {
        TreeNode<T> left;
        TreeNode<T> right;
        T item;

        TreeNode(T item) {
            this.item = item;
        }
    }

    public void createBinaryTree(T[] arr) {
        ...
        root = new TreeNode<T>(arr[0]);

        Queue<TreeNode<T>> queue =
            new LinkedList<TreeNode<T>>();
        ...
        for (int i = 0; i < half; i++) {
            if (arr[i] != null) {
                TreeNode<T> current = queue.poll();
                ...
                if (arr[left] != null) {
                    current.left = new TreeNode<T>(arr[left]);
                    queue.add(current.left);
                }
                ...
            }
        }
    }

    private static class LCAData<T> {
        TreeNode<T> lca;
        ...
    }

    public T leastCommonAncestor(T n1, T n2) {
        LCAData<T> lcaData = new LCAData<T>(0);

        foundMatchAndDuplicate(root, lcaData, n1, n2, 
            new HashSet<T>());
        ...
    }

    private boolean foundMatchAndDuplicate(TreeNode<T> node, 
            LCAData<T> lcaData, T n1, T n2, Set<T> set) {
        ...
    }
}

    (Effective Java 2nd Edition, Item 26: Favor generic types and Item 27: Favor generic methods)

\$\endgroup\$

Your Answer

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

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