Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

BinaryTreeLevelOrderTraversal.java

    public List<List<Integer>> levelOrder(TreeNode root) {
        // Tree maps keep a strict ordering of the values wtr to the order in which
        // there inserted, necessary for keeping the level lists in order
        Map<Integer, List<Integer>> treeList = new TreeMap<Integer, List<Integer>>();
        int level = 0;
        
        if(root != null){
            List<Integer> rootLevelList = new ArrayList<Integer>(1);
            
            rootLevelList.add(root.val);
            treeList.put(level, rootLevelList);
            
            // same list with updates
            treeList = levelTraverse(root, level + 1, treeList);
        }
        
        List<List<Integer>> result = new ArrayList<List<Integer>>(treeList.values());
        
        return result;
    }
    
    public Map<Integer, List<Integer>> levelTraverse(TreeNode root, int level, Map<Integer, List<Integer>> treeList){
        List<Integer> levelList;
        
        if(root == null){
            return null;
        }
        
        if(root.left != null){
            levelList = treeList.get(level);
            
            // if the level list didnt exist add it to the tree list
            if(levelList == null){
                levelList = new ArrayList<Integer>();
                treeList.put(level, levelList);
            }
            
            // add the node at this level the level list
            levelList.add(root.left.val);
            
            levelTraverse(root.left, level + 1, treeList);
        }
        
        if(root.right != null){
            levelList = treeList.get(level);
            
            // if the level list didnt exist add it to the tree list
            if(levelList == null){
                levelList = new ArrayList<Integer>();
                treeList.put(level, levelList);
            }
            
            // add the node at this level the level list
            levelList.add(root.right.val);
            
            levelTraverse(root.right, level + 1, treeList); 
        }
        
        return treeList;
    }