LevelOrderTraversalUsingDFSWithMap.java

public void dfsHelper(TreeNode node, int depth, Map<Integer, List<Integer>> depthToListMap) {
    if (node == null) {
        return;
    }

    if (!depthToListMap.containsKey(depth)) {
        depthToListMap.put(depth, new ArrayList<Integer>());
    }
    depthToListMap.get(depth).add(node.val);
    dfsHelper(node.left, depth + 1, depthToListMap);
    dfsHelper(node.right, depth + 1, depthToListMap);

}

// this is a clever way to implement level order traversal using dfs with the help of a map to keep overwriting the
// depth info
public List<List<Integer>> levelOrderDfs(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    Map<Integer, List<Integer>> depthToListMap = new HashMap<>();

    this.dfsHelper(root, 1, depthToListMap);

    int i = 1;

    while (depthToListMap.containsKey(i)) {
        res.add(depthToListMap.get(i));
        i++;
    }

    return res;
}