Print all nodes that are at distance k from a leaf node Given a binary tree and a positive integer \$k\$, print all nodes that
  are distance \$k\$ from a leaf node.
  
  Here, the meaning of distance is different from the previous post.
  Here, \$k\$ is the distance from a leaf means \$k\$ levels higher than
  a leaf node. For example, if \$k\$ is more than height of binary tree,
  then nothing should be printed. Expected time complexity is \$O(n)\$
  where \$n\$ is the number nodes in the given binary tree.
  
  


I'm looking for code review, optimizations and best practices.  I'm verifying \$O(n)\$ to be both the time and space complexity.

public class KDistanceFromLeaves&lt;T&gt; {

    private TreeNode&lt;T&gt; root;

    public KDistanceFromLeaves(List&lt;T&gt; items) {
        create(items);
    }

    private void create (List&lt;T&gt; items) {
        root = new TreeNode&lt;T&gt;(items.get(0));

        final Queue&lt;TreeNode&lt;T&gt;&gt; queue = new LinkedList&lt;TreeNode&lt;T&gt;&gt;();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i &lt; half; i++) {
            if (items.get(i) != null) {
                final TreeNode&lt;T&gt; current = queue.poll();                
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode&lt;T&gt;(items.get(left));
                    queue.add(current.left);
                }
                if (right &lt; items.size() &amp;&amp; items.get(right) != null) {
                    current.right = new TreeNode&lt;T&gt;(items.get(right));
                    queue.add(current.right);
                }
            }
        }
    }

    public static class TreeNode&lt;T&gt; {
        private TreeNode&lt;T&gt; left;
        private T item;
        private TreeNode&lt;T&gt; right;

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


    public List&lt;T&gt; kDistanceFromLeaf(int k) {
        final List&lt;T&gt; list = new ArrayList&lt;&gt;();
        final List&lt;Boolean&gt; booleanList = new ArrayList&lt;&gt;();
        recurse(root, k, new ArrayList&lt;T&gt;(), list, booleanList);
        return list;
    }

    private void recurse(TreeNode&lt;T&gt; node, int k, List&lt;T&gt; items, List&lt;T&gt; list, List&lt;Boolean&gt; visited) {

        if (node == null) return;

        if (node.left == null &amp;&amp; node.right == null &amp;&amp; k &lt;= items.size() &amp;&amp; !visited.get(items.size() - k)) {
                list.add(items.get(items.size() - k));
                visited.set(items.size() - k, true);
        }

        items.add(node.item);
        visited.add(false);

        recurse(node.left, k, items, list, visited);
        recurse(node.right, k, items, list, visited);

        items.remove(items.size() - 1); 
        visited.remove(visited.size() - 1);
    }
}

public class KDistanceFromLeavesTest {

    @Test
    public void testCompleteTree() {
        KDistanceFromLeaves&lt;Integer&gt; kd = new KDistanceFromLeaves&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        assertEquals(Arrays.asList(2, 3), kd.kDistanceFromLeaf(1));
        assertEquals(Arrays.asList(1), kd.kDistanceFromLeaf(2));
        assertEquals(Collections.EMPTY_LIST, kd.kDistanceFromLeaf(3));
        assertEquals(Collections.EMPTY_LIST, kd.kDistanceFromLeaf(4));
    }


    @Test
    public void testInCompleteTree() {
        KDistanceFromLeaves&lt;Integer&gt; kd1 = new KDistanceFromLeaves&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, null, null, null, null, 6, 7));
        assertEquals(Arrays.asList(2, 5, 1), kd1.kDistanceFromLeaf(1));
        assertEquals(Arrays.asList(1, 2), kd1.kDistanceFromLeaf(2));
        assertEquals(Arrays.asList(1), kd1.kDistanceFromLeaf(3));
        assertEquals(Collections.EMPTY_LIST, kd1.kDistanceFromLeaf(4));
    }
}
Your algorithm seems fine; it is indeed \$O(n)\$ time and \$O(n)\$ space. If you adjusted your code somewhat, you could reduce it to \$O(h)\$ space (ignoring input), where \$h\$ is the height of the tree; I'll come back to this later. One nit: it doesn't handle k == 0.

The major issue with this code is that it doesn't help the reader understand it. Your names describe the mechanics of the named item, not its purpose (recurse, list, items -- what purpose do these have in your algorithm?). The classes are divided oddly -- encapsulation is broken (e.g. almost all of your code has to know the precise representation of the tree).



Encapsulation of the tree representation

KDistanceFromLeaves&lt;T&gt;'s constructor takes a List&lt;T&gt;. Here you're making assumptions about the representation of the tree that have nothing to do with its type. The easiest solution is probably to take a TreeNode&lt;T&gt; instead (and make TreeNode&lt;T&gt; a public class instead of a nested class of KDistanceFromLeaves&lt;T&gt;. Alternatively, you could implement something like

interface IterableTree&lt;T&gt; {
    interface Iterator {
        T getValue();
        boolean hasLeft();
        /** The behavior of getLeft() is undefined when !hasLeft() */
        Iterator getLeft();
        /** The behavior of getRight() is undefined when !hasRight() */
        boolean hasRight();
        Iterator hasRight();
    }
    boolean isEmpty();
    /** The behavior of getRoot() is undefined when isEmpty(). */
    Iterator getRoot();
}


Two implementations arise immediately to mind:

class TreeNode&lt;T&gt; implements IterableTree&lt;T&gt;, IterableTree&lt;T&gt;.Iterator {
    private final T value;
    private TreeNode&lt;T&gt; left = null;
    private TreeNode&lt;T&gt; right = null;

    public TreeNode(T value) { this.value = value; }
    public void setLeft(TreeNode&lt;T&gt; left) { this.left = left; }
    public void setRight(TreeNode&lt;T&gt; right) { this.right = right; }

    /** A non-null TreeNode&lt;T&gt; is never an empty tree */ 
    @Override
    public boolean isEmpty() { return false; }

    @Override
    public TreeNode&lt;T&gt; getRoot() { return this; }

    @Override
    public T getValue() { return value; }

    @Override
    public TreeNode&lt;T&gt; getLeft() { return left; }

    @Override
    public boolean hasRight() { return right != null; }

    @Override
    public TreeNode&lt;T&gt; getRight() { return right; }
}

public ListBackedTree&lt;T&gt; implements IterableTree&lt;T&gt; {
    private final List&lt;T&gt; nodes;

    public ListBackedTree(List&lt;T&gt; nodes) { this.nodes = nodes }

    private class Iterator implements IterableTree&lt;T&gt;.Iterator {
        private int index;

        public Iterator(int index) { this.index = index; }

        @Override
        public T getValue() { return nodes.get(index); }

        @Override
        public boolean hasLeft() { return 2 * index + 1 &lt; nodes.size(); }

        @Override
        public Iterator getLeft() {
            return new Iterator(2 * index + 1);
        }

        @Override
        public boolean hasRight() { return 2 * index + 2 &lt; nodes.size(); }

        @Override
        public Iterator getRight() {
            return new Iterator(2 * index + 2);
        }
    }

    @Override
    public boolean isEmpty() { return nodes.isEmpty(); }

    @Override
    public Iterator getRoot() { return new Iterator(0); }
}


If you use IterableTree&lt;T&gt; instead of List&lt;T&gt;, your users don't have to convert between tree representations just to use your algorithm -- they can use whatever tree they've already got lying around.

As a side note, from an encapsulation point of view, with the code you had, create should be a static method on TreeNode&lt;T&gt; (or even be renamed to TreeNode&lt;T&gt;.TreeNode(List&lt;T&gt;)), not a private method on KDistanceFromTreeLeaves&lt;T&gt;. Classes should be responsible for understanding their own representation.



Rewriting the algorithm

As I mentioned above, your algorithm is fine. The problem comes in the way it is presented.

I'd start by making kDistanceFromLeaf a static method that takes a tree as an argument rather than a method on a class whose only member is a tree. It sort of made sense with your code, since you transformed the tree passed to the constructor and so wanted to save the effort of transformation each time you called your algorithm. However, your transformation was simply a change in representation -- you don't do any additional computation. Thus, it makes more sense to abstract the algorithm away from the representation than to transform the data and make your algorithm depend on a single representation.

How about the return value? A List is ordered and may contain multiple copies of a given value. That doesn't really model our return value. What we really want to return is a Set -- this is an unordered collection that contains at most one copy of each value.

Next up is naming. What is items? Well, it's a list of the current node's ancestors. So let's call it ancestors. What about list? This is a list of the nodes that satisfy our condition. We could call it found or targets. visited is obviated by using a Set instead of a List.

Finally, comments. First, it is sensible to document the purpose of classes and methods using doc comments. Second, it is sometimes very useful to add comments that explain why code is written a certain way.

With all that in mind, here's another whack at implementing the algorithm:

/** Collects implementations of interview questions */
class InterviewProblems {
    /**
     * Given a tree, determines which nodes are exactly k distance from
     * a leaf node (that is, nodes that are k levels above a leaf node).
     */
    public static &lt;T&gt; Set&lt;T&gt; kDistanceFromLeaf(
            IterableTree&lt;T&gt; tree, int k) {
        Set&lt;T&gt; found = new HashSet&lt;&gt;();
        if (tree == null || tree.isEmpty()) return found;
        computeKDistanceFromLeaf(tree.getRoot(), k, new ArrayList&lt;T&gt;(), found);
        return found;
    }

    private static &lt;T&gt; boolean isLeafNode(IterableTree&lt;T&gt;.Iterator node) {
        return !node.hasLeft() &amp;&amp; !node.hasRight();
    }

    /** Recursive helper function for {@link #kDistanceFromLeaf}. */
    private static &lt;T&gt; void computeKDistanceFromLeaf(
            IterableTree&lt;T&gt;.Iterator node, int k,
            List&lt;T&gt; ancestors, Set&lt;T&gt; found) {
        ancestors.add(node.getValue());
        // If this is a leaf node, its kth ancestor should be added to found.
        if (isLeafNode(node) &amp;&amp; ancestors.size() &gt; k) {
            found.add(ancestors.get(ancestors.size() - 1 - k));
        }
        if (node.hasLeft())
            computeKDistanceFromLeaf(node.getLeft(), k, ancestors, found);
        if (node.hasRight())
            computeKDistanceFromLeaf(node.getRight(), k, ancestors, found);
        ancestors.remove(ancestors.size() - 1);
    }
}




Minor comments

You use final a lot for local variables. That's fine (and as someone who uses C++ a lot, I certainly understand the instinct). However, a more common Java style is only to mark local variables final when they are to be used by inner classes. final is not nearly as useful as C++'s const and the cost-benefit tradeoff (cost: final is sprinkled liberally through the code; benefit: you know that the reference won't be reassigned, but not that the objects won't be modified) is less in favor of adding final in Java than const in C++.

Yay unit tests! One question: You've given an example in the problem description -- why not write a unit test that confirms that the code correctly works the example?

A final comment: I haven't compiled, much less tested, the code in this example, so use it with care and let me know if you have any questions!