8
\$\begingroup\$

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.

diagram

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<T> {

    private TreeNode<T> root;

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

    public static class TreeNode<T> {
        private TreeNode<T> left;
        private T item;
        private TreeNode<T> right;

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


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

    private void recurse(TreeNode<T> node, int k, List<T> items, List<T> list, List<Boolean> visited) {

        if (node == null) return;

        if (node.left == null && node.right == null && k <= items.size() && !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<Integer> kd = new KDistanceFromLeaves<Integer>(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<Integer> kd1 = new KDistanceFromLeaves<Integer>(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));
    }
}
\$\endgroup\$
11
\$\begingroup\$

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<T>'s constructor takes a List<T>. 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<T> instead (and make TreeNode<T> a public class instead of a nested class of KDistanceFromLeaves<T>. Alternatively, you could implement something like

interface IterableTree<T> {
    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<T> implements IterableTree<T>, IterableTree<T>.Iterator {
    private final T value;
    private TreeNode<T> left = null;
    private TreeNode<T> right = null;

    public TreeNode(T value) { this.value = value; }
    public void setLeft(TreeNode<T> left) { this.left = left; }
    public void setRight(TreeNode<T> right) { this.right = right; }

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

    @Override
    public TreeNode<T> getRoot() { return this; }

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

    @Override
    public TreeNode<T> getLeft() { return left; }

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

    @Override
    public TreeNode<T> getRight() { return right; }
}

public ListBackedTree<T> implements IterableTree<T> {
    private final List<T> nodes;

    public ListBackedTree(List<T> nodes) { this.nodes = nodes }

    private class Iterator implements IterableTree<T>.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 < nodes.size(); }

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

        @Override
        public boolean hasRight() { return 2 * index + 2 < 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<T> instead of List<T>, 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<T> (or even be renamed to TreeNode<T>.TreeNode(List<T>)), not a private method on KDistanceFromTreeLeaves<T>. 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 <T> Set<T> kDistanceFromLeaf(
            IterableTree<T> tree, int k) {
        Set<T> found = new HashSet<>();
        if (tree == null || tree.isEmpty()) return found;
        computeKDistanceFromLeaf(tree.getRoot(), k, new ArrayList<T>(), found);
        return found;
    }

    private static <T> boolean isLeafNode(IterableTree<T>.Iterator node) {
        return !node.hasLeft() && !node.hasRight();
    }

    /** Recursive helper function for {@link #kDistanceFromLeaf}. */
    private static <T> void computeKDistanceFromLeaf(
            IterableTree<T>.Iterator node, int k,
            List<T> ancestors, Set<T> found) {
        ancestors.add(node.getValue());
        // If this is a leaf node, its kth ancestor should be added to found.
        if (isLeafNode(node) && ancestors.size() > 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!

\$\endgroup\$
  • \$\begingroup\$ Good answer. But you would want a defensive copy of nodes in ListBackedTree IRL and that would make the algorithm \$O(n)\$ space anyways. \$\endgroup\$ – abuzittin gillifirca Sep 12 '14 at 13:44
  • \$\begingroup\$ I'm not so sure that's the case. Certainly if you were writing a wrapper around this function that takes a list you'd need a defensive copy to be safe. If, on the other hand, the lack of copy is well documented and you use the IterableTree interface everywhere in your code (except in one method that obtains the list somehow and returns an IterableTree), you might avoid the copy. \$\endgroup\$ – ruds Sep 14 '14 at 17:37
6
\$\begingroup\$

I think your code looks good. I just found readability as issue. It can be fixed by simply rewriting the code and renaming the variables. For example, instead of using items, I would use path. Good part about your algorithm is that you have used lists (i.e. items list and visited) so you don't have to worry about sizes etc, but arrays have their own advantages as your can use indices.

Coming on the algorithm side, I think it is more or loss same - time complexity is \$O(n)\$ and space complexity is \$O(n)\$.

From the design side, I think @ruds has given a really good solution.

kodeknight has a good solution. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.

We will traverse through the tree, and as soon as we hit a leaf node, we will check if some node exists in path at k distance away i.e. (currPathLength - k - 1 > 0). If it exists we will print it, only if it is not already visited.

In case node is not a leaf node, we will recurse on the left and right sub tree, repeating the above step.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Thank you for revising your answer — it now explains your thought process much better. I've removed the cited code since it doesn't appear to be your own work. \$\endgroup\$ – 200_success Sep 4 '15 at 0:16
5
\$\begingroup\$

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