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.