Deepest left leaf node in a binary tree

Question

Given a Binary Tree, find the deepest leaf node that is left child of its parent. This question is attributed to GeeksForGeeks. Looking for code-review, optimizations and best practices.

public class DeepestLeftLeaf<T> {

    private TreeNode<T> 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 DeepestLeftLeaf(List<T> items) {
        create(items);
    }

    private void create (List<T> items) {
        root = new TreeNode<T>(items.get(0));

        final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode<T> current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode<T>(items.get(left));
                    queue.add(current.left);
                }
                if (right < items.size() && items.get(right) != null) {
                    current.right = new TreeNode<T>(items.get(right));
                    queue.add(current.right);
                }
            }
        }
    }

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

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

    /**
     * Returns the deepest left-leaves. 
     * If two such left-child-leaves are at equidistant, we chose the leftmost among them in the tree.
     * 
     * @return  the item which is deepest.
     */
    public T leftNode() {
        if (root == null) {
            throw new IllegalStateException("The root cannot be null.");
        }
        return recurse(root).item;
    }

    private static class Data<T> {
        private int count;
        private T item;
        Data (int count, T item) {
            this.count = count;
            this.item =  item;
        }
    }


    private Data<T> recurse(TreeNode<T> node) {
        if (node == null) return null;

        Data<T> data1;
        if (node.left != null && node.left.left == null && node.left.right == null) {
            data1 = new Data<>(1, node.left.item);
        } else {
            data1 = recurse(node.left);
        }

        Data<T> data2 = recurse(node.right);

        if (data1 == null && data2 == null) return null;

        if (data1 == null || data2 == null) {
            Data<T> dataTemp = data1 != null ? data1 : data2;
            dataTemp.count++;
            return dataTemp;
        }

        if (data1.count >= data2.count) { 
            data1.count++;
            return data1;
        } else {
            data2.count++;
            return data2;
        }
    }
}


public class DeepestLeftLeafTest {

    @Test
    public void test1() {
        DeepestLeftLeaf<Integer> deepestLL1 = new DeepestLeftLeaf<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
        assertEquals(8, (int)deepestLL1.leftNode());
    }

    @Test
    public void test2() {
        DeepestLeftLeaf<Integer> deepestLL2 = new DeepestLeftLeaf<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        assertEquals(4, (int)deepestLL2.leftNode());
    }

    @Test
    public void test3() {
        DeepestLeftLeaf<Integer> deepestLL3 = new DeepestLeftLeaf<Integer>(Arrays.asList(1, 2, 3, null, 5, 6, 7));
        assertEquals(6, (int)deepestLL3.leftNode());
    }

    @Test
    public void test4() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, null, 5, 6, null, null, null, null, null, 7, null, 8, null,
                null, null, null, null, null, null, null, null, null, 9, null, null, null, null, 10);
        DeepestLeftLeaf<Integer> deepestLL4 = new DeepestLeftLeaf<Integer>(list);
        assertEquals(9, (int) deepestLL4.leftNode());
    }

}

Answer 1

Your recursion is doing far too much, and it can be simplified a lot.

Additionally, you are creating a lot of Data instances, when a simpler mechanism would be to call it a Result<T> and reuse that single node for all values....

private class Result<T> {
    int depth;
    T data;
}

Then, as you recurse, you have a single instance of that Result object that you pass to all nodes on the recursion...

private void recurse(Result<T> result, TreeNode<T> node, int depth, boolean isLeft) {
    if (node == null) {
        // nothing to do
        return;
    }
    if (isleft && node.left == null && node.right == null) {
        // we are the left leaf node
        if (depth > result.depth) {
            result.depth = depth;
            result.data = node.item;
        }
    }
    recurse(result, node.left, depth + 1, true);
    recurse(result, node.right, depth + 1, false);
}

This algorithm makes the process a lot cleaner, and makes the recursion more obvious.

Answer 2

Bug:

IndexOutOfBoundsException on empty list in DeepestLeftLeaf.create(List<T> items). You don't have a comment stating you need to input a list containing at least something. Consider returning IllegalArgumentException and adding a comment.