Creating an Array of Linked Lists from a BST 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&lt;LinkedList&lt;Node&gt;&gt; makeArrayList(Node n) {
        int level = 0;
        return addLists(new ArrayList&lt;LinkedList&lt;Node&gt;&gt;(), n, level);
    }

    ArrayList&lt;LinkedList&lt;Node&gt;&gt; addLists(ArrayList&lt;LinkedList&lt;Node&gt;&gt; arr, Node n, int level) {
        if (n != null) {
            if (arr.get(level) == null) {
                LinkedList&lt;Node&gt; newList = new LinkedList&lt;Node&gt;();
                arr.add(level, newList);
            }
            LinkedList&lt;Node&gt; nodeList = arr.get(level);
            nodeList.add(n);
            addLists(arr, n.leftChild, level + 1);
            addLists(arr, n.rightChild, level + 1);
        }
        return arr;
    }
}
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&lt;Node&gt; 
List&lt;List&lt;Node&gt;&gt;


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&lt;Node&gt;());

    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.