Deepest left leaf node in a binary tree

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 {

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

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

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

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

for (int i = 0; i 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.get(right));
queue.add(current.right);
}
}
}
}

private static class TreeNode {
private TreeNode left;
private T item;
private TreeNode 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 {
private int count;
private T item;
Data (int count, T item) {
this.count = count;
this.item = item;
}
}

private Data

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 and reuse that single node for all values....

private class Result {
    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 result, TreeNode 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.

StackExchange Code Review Q#57742, answer score: 6