Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 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
5  
I haven't test it then do it. – tb- Mar 1 at 22:32

1 Answer

up vote 3 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

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.