#ctci

BTLists.java

// this can be achieved by either depth first traversal or breadth first traversal
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BTLists{
    // for depth first, we can use pre-order traversal
    public ArrayList<LinkedList<Node>> convertTreeToLists(Node root){
        ArrayList<LinkedList<Node>> result = new ArrayList<LinkedList<Node>>();
        convertTreeToLists(root, result, 0);
        return result;
    }
    
    private void convertTreeToLists(Node root, ArrayList<LinkedList<Node>> result, int level){
        if(root == null) return;
        
        if(level == result.size()){
            // then this is a new level
            LinkedList<Node> list = new LinkedList<Node>();
            list.add(root);
            result.add(list);
        }else{
            result.get(level).add(root);
        }
        convertTreeToLists(root.left, result, level + 1);
        convertTreeToLists(root.right, result, level + 1);
    }
    
    // for depth first, we can create a Wrapper class for the node or use two queues
    public ArrayList<LinkedList<Node>> convertTreeToListsBFS(Node root){
        ArrayList<LinkedList<Node>> result = new ArrayList<LinkedList<Node>>();
        if(root == null) return result;
        
        Queue<Node> nodes = new LinkedList<Node>();
        Queue<Integer> levels = new LinkedList<Integer>();
        
        nodes.offer(root);
        levels.offer(0);
        
        Node current = null;
        int currentLv = 0;
        int prevLv = -1;
        while(!nodes.isEmpty()){
            current = nodes.poll();
            currentLv = levels.poll();
            
            if(currentLv == prevLv){
                // same level
                result.get(currentLv).add(current);
            }else{
                LinkedList<Node> list = new LinkedList<Node>();
                list.add(node);
                result.add(list);
                prevLv = currentLv;
            }
            
            if(current.left){
                nodes.offer(current.left);
                levels.offer(currentLv + 1);
            }
            
            if(current.right){
                nodes.offer(current.right);
                levels.offer(currentLv + 1);
            }
        }
        
        return result;
    } 
}