3
\$\begingroup\$

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

}
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.