# Check if all leaves are at same level

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

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

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

}

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

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

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.

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