# 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<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>>();

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));
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(items.get(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());
}

}


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.

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.