Haseeb Javed Haseeb Javed - 1 month ago 8
Java Question

Java - Convert a Tree to a Lists of Nodes with same depth

I am trying to write a code to convert a binary tree to a lists of nodes with same depth. If a tree has depth d, then d lists will be created. The logic is to do in-order traversal and add the currently traversed node to the list of appropriate depth.

public void treeToListofNodesByLevel(Node<T> n,int depth, ArrayList<LinkedList<Node<T>>> treeList){

if(n.right != null){
inOrderWithHeight(n.right, depth + 1);
}
if(treeList.size() >= depth){
treeList.add(depth, new LinkedList<Node<T>>() );
}
treeList.get(depth).add(n);
if(n.left != null){
inOrderWithHeight(n.left, depth + 1);
}

}


and then calling:

ArrayList<LinkedList<Node<T>>> result = new ArrayList<LinkedList<Node<T>>>();
treeToListofNodesByLevel(root, 0, result);


Will this work ? Are there any corner cases I am not handling ?
Also, right now I am passing the List of List to be returned by the method because I can not think of a way to initialize it in the method and returning it at then end while also maintaining the recursive structure. Is there a better way to do this ?

Answer

You have the general concept pretty much perfect. It will work, and should handle all cases.

However, you have a few errors in the details:

  • Your check for when to add a new list has the comparison in the wrong direction. It should be if (treeList.size() <= depth).
  • Each call to inOrderWithHeight() (which you haven't provided any code of) should be a recursive call to treeToListofNodesByLevel(). Keep the first two arguments as they are, and just pass the treeList for the third.
  • This one's more a style issue, but parameter types should generally be declared as the highest level type that satisfies what you actually need. There is no need here to specify ArrayList or LinkedList, any List will do. Change the treeList parameter's type to List<List<Node<T>>>.

For the matter of initializing the List inside the method while also using recursion, that's the sort of thing that implementation helper methods are for. Take the current body of treeToListofNodesByLevel and move it into a private method (with the recursive calls changed so the private method calls itself), let's call it treeToListofNodesByLevelHelper. Then change the current public method to this:

public List<List<Node<T>>> treeToListofNodesByLevel(Node<T> node) {
    List<List<Node<T>>> result = new ArrayList<>();
    treeToListofNodesByLevelHelper(node, 0, result);
    return result;
}