Creating an Array of Linked Lists from a BST

Question

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;
    }
}

\$\begingroup\$ I haven't test it then do it. \$\endgroup\$

tb-
– tb-

2013-03-01 22:32:36 +00:00
Commented Mar 1, 2013 at 22:32 — tb-
– tb-, Commented Mar 1, 2013 at 22:32

Chris Hayes · Accepted Answer · 2013-12-28 09:21:13Z

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.

mheinzerling · Accepted Answer · 2013-03-02 08:07:05Z

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.

Stack Exchange Network

Creating an Array of Linked Lists from a BST

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Creating an Array of Linked Lists from a BST

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions