1
\$\begingroup\$

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

}
\$\endgroup\$
3
\$\begingroup\$

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));
    }
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ You will likely visit each node many times. This recursion is O(D^2), where D is the depth of the tree. \$\endgroup\$ – 200_success Jul 30 '14 at 7:09
  • \$\begingroup\$ In Java, it's null, not nil. \$\endgroup\$ – 200_success Jul 30 '14 at 7:10
  • \$\begingroup\$ Yes, this algorithm is not efficient. However, for unit test code, it's probably sufficient. (Also, fixed the null, too many languages!). \$\endgroup\$ – Greg Hewgill Jul 30 '14 at 7:23

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.