Check if all leaves are at same level

Question

Check if all leaves are at same level. This question is attributed to geek for geeks. Looking for code-review, optimization and best practices.

public class LeavesLevel<T> {

    private TreeNode<T> root;

    public LeavesLevel(List<T> items) {
        create (items);
    }

    private void create (List<T> items) {        
        root = new TreeNode<>(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;
        }
    }

    public boolean refurbish() {
        return recurse (root, 0,  new NodeDepth(-1));
    }

    private static class NodeDepth {
        private int depth;
        NodeDepth(int depth) {
            this.depth = depth;
        }
    }

    public boolean recurse(TreeNode<T> node, int leafLevel, NodeDepth nodeDepth) {
        if (node == null) {
            return true;
        }

        if (node.left == null && node.right == null) {
           if (nodeDepth.depth == -1) {
               nodeDepth.depth = leafLevel;
               return true; // if tree contains a single leaf node, then 
           }
           return leafLevel == nodeDepth.depth;
        }

        return recurse (node.left, leafLevel + 1, nodeDepth) && recurse (node.right, leafLevel + 1, nodeDepth);
    }
}


public class LeafLevelTest {

    @Test
    public void test1() {
        /**
         * 
         *           12
                   /    \
                 5       7       
               /          \ 
              3             1
         * 
         */
        LeavesLevel<Integer> ll1 = new LeavesLevel<>(Arrays.asList(1, 5, 7, 3, null, null, 1)); 
        assertTrue(ll1.refurbish());
    }

    @Test
    public void test2() {
        /**
         *       12
                /    \
              5       7       
             /          
            3          
         * 
         */
        LeavesLevel<Integer> ll2 = new LeavesLevel<>(Arrays.asList(1, 5, 7, 3)); 
        assertFalse(ll2.refurbish());
    }

    @Test
    public void test3() {
        /**
         * 
         * 
                    12
                    /    
                  5             
                /   \        
               3     9
              /      /
             1      2
         * 
         * 
         */
        LeavesLevel<Integer> ll3 = new LeavesLevel<>(Arrays.asList(1, 5, null, 3, 9, null, null, 1, null, 2)); 
        assertTrue(ll3.refurbish());
    }

}

Answer 1

Code reuse

You've asked a few dozen questions about tree algorithms, many of which contain very similar code. Copy-and-paste programming is an antipattern; copy-and-pasting with modifications here and there is even worse. By now, you should have developed a library of reusable classes.

That means decomposing your classes to obey the Single Responsibility Principle. There should be a TreeNode<T> class that acts as a generic node with two child pointers, and possibly a create(List<? extends T>) convenience method.

public class TreeNode<T> {
    public TreeNode<T> left, right;
    public final T item;

    public TreeNode(T item) {
        this.item = item;
    }

    public static <T> TreeNode<T> createTree(List<? extends T> items) {
        TreeNode<T> root = new TreeNode<>(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);
                }
            }
        }
        return root;
    }
}

There should be a TreePredicate<T> interface for algorithms that test a tree and return a true/false result.

interface TreePredicate<T> {
    boolean test(TreeNode<T> root);
}

Algorithms that implement the TreePredicate<T> interface should be in classes that are named as nouns, as with all Java classes.

Algorithm

Your use of recursion is weird.

The methods are poorly named: refurbish() is unintuitive; recurse() is too generic. Furthermore, recurse() looks like a helper function that should not have been made public.

You shouldn't use mutation with recursion. A key advantage of recursion is that immutable stack values make it easy to extend local reasoning to the large scale. Impure functions with side-effects make such analysis difficult.

It should be clear what the invariants are when you recurse. See the example JavaDoc below.

public class UniformLeafDepthPredicate<T> implements TreePredicate<T> {

    public boolean test(TreeNode<T> root) {
        return allLeavesDepth(root) >= 0;
    }   

    /**
     * Returns the depth of this node, if the paths to all of its descendant
     * leaf nodes are all of the same length, or -1 if the height is
     * non-uniform.  The depth of a leaf node is 1.
     */
    private int allLeavesDepth(TreeNode<T> node) {
        if (node == null) return 0;

        int lDepth = allLeavesDepth(node.left);
        if (lDepth < 0) return -1;          // LHS has non-uniform depth
        int rDepth = allLeavesDepth(node.right);
        if (rDepth < 0) return -1;          // RHS has non-uniform depth

        if (lDepth == 0) return 1 + rDepth; // Only R child; RHS has uniform depth
        if (rDepth == 0) return 1 + lDepth; // Only L child; LHS has uniform depth

        return (lDepth == rDepth) ? 1 + lDepth : -1;
    }   
}

By following these guidelines for recursion, the code is greatly simplified.

Unit tests

I don't know why you labelled the root node as "12" in your comments. It's inconsistent with your actual tests.

I suggest adding one more test, because you currently have no test in which a child node has non-uniform depth.

public class LeafLevelTest {

    private TreePredicate<Integer> tester = new UniformLeafDepthPredicate<>();

    …

    @Test
    public void test4() {
        /*
                   1
                  /
                 5
                / \
               3   9
              /
             4
         */
        TreeNode<Integer> ll4 = TreeNode.createTree(Arrays.asList(1, 5, null, 3, 9, null, null, 4));
        assertFalse(tester.test(ll4));
    }
}

Answer 2

A minor bug: You get an IndexOutOfBoundsException for an empty list in LeavesLevel.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.

Answer 3

To determine whether a tree has all leaves at the same level, it is sufficient to check that

depth(node.left) == depth(node.right)

for all nodes. So you can do this something like:

boolean leaves_same_level(TreeNode<T> node)
{
    return depth(node.left) == depth(node.right)
        && leaves_same_level(node.left)
        && leaves_same_level(node.right);
}

int depth(TreeNode<T> node)
{
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(depth(node.left), depth(node.right));
}