current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

Question

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists)

Here is my attempt at a solution. I haven't test it, but I was trying to get feedback on whether or not this would be an appropriate approach to such solution.

public class solution {

    ArrayList<LinkedList<Node>> makeArrayList(Node n) {
        int level = 0;
        return addLists(new ArrayList<LinkedList<Node>>(), n, level);
    }

    ArrayList<LinkedList<Node>> addLists(ArrayList<LinkedList<Node>> arr, Node n, int level) {
        if (n != null) {
            if (arr.get(level) == null) {
                LinkedList<Node> newList = new LinkedList<Node>();
                arr.add(level, newList);
            }
            LinkedList<Node> nodeList = arr.get(level);
            nodeList.add(n);
            addLists(arr, n.leftChild, level + 1);
            addLists(arr, n.rightChild, level + 1);
        }
        return arr;
    }
}
share|improve this question
9  
I haven't test it then do it. –  tb- Mar 1 '13 at 22:32
add comment

2 Answers

up vote 3 down vote accepted

This section:

if (arr.get(level) == null) {
    LinkedList<Node> newList = new LinkedList<Node>();
    arr.add(level, newList);
}

is going to throw an IndexOutOfBoundsException every single time, since you never do arr.add before doing arr.get. The proper way to do it (incorporating some good suggestions from @mnhg's answer):

{
    if (n == null) return arr;
    if (arr.size() <= level) arr.add(new LinkedList<Node>());

    arr.get(level).add(n);
    addLists(arr, n.leftChild, level + 1);
    addLists(arr, n.rightChild, level + 1);

    return arr;
}

This, of course, is why we test code before sending it for review.

share|improve this answer
add comment
up vote 7 down vote

Your return types and the types left of the assignments should be as general as possible, so you only need to change the instantiation if you want to change the implementation to an other type of list.

List<Node> 
List<List<Node>>

In general it is a good idea to replace ifs that covers the whole function by a guard condition. So you get rid of a level of nesting.

{
    if (n == null) return arr;
    if (arr.get(level) == null) arr.add(level, new LinkedList<Node>());

    arr.get(level).add(n);
    addLists(arr, n.leftChild, level + 1);
    addLists(arr, n.rightChild, level + 1);

    return arr;
}

I only checked your code layout. If you want to see if it works, write a test as tb suggested.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.