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.