Given binary tree create linkedlist of all the nodes at each depth (BFS or DFS)

Question

I am trying to figure out the solution for the above given problem. I came up with a solution, but I am not sure if that will work successfully.

public Node LinkedListOfNodes(Node root, Map<Integer, LinkedList<Node>> mapOfLinkedList, int level)
    {

        if(root == null) {
            return null;
        }

        final LinkedList<Node> linkedListOfNodes = new LinkedList();
        level = level+1;

        linkedListOfNodes.add(LinkedListOfNodes(root.left, mapOfLinkedList, level));
        linkedListOfNodes.add(LinkedListOfNodes(root.right,mapOfLinkedList,level));

        mapOfLinkedList.put(level,linkedListOfNodes);

        return root;
    }

Is this solution right? Can a better approach be taken? Can a BFS approach be the right approach here or DFS will work better?

This is how I had implemented BFS. I can modify it to work for this problem.

public void BFS(Graph graph, Vertex source) {

        final Queue<Vertex> queue = new PriorityQueue();

        for(Vertex vertex : graph.vertices) {
            vertex.color = "WHITE";
            vertex.distance = 0;
            vertex.parent = null;
        }

        source.distance = 0;
        source.parent = null;
        source.color = "GRAY";

        queue.add(source);

        while(!queue.isEmpty())
        {
            Vertex u = queue.element();
            for (Vertex vertex : graph.adj.get(u))
            {
                if (vertex.color == "WHITE")
                {
                    vertex.color = "GRAY";
                    vertex.distance = vertex.distance + u.distance;
                    vertex.parent = u;

                    queue.add(vertex);
                }
            }

            u.color = "BLACK";
        }

    }


    class Graph {

        List<Vertex> vertices;
        Map<Vertex, List<Vertex>> adj;
    }

    class Vertex {
        int distance;
        Vertex parent;
        String color;
    }

Answer 1

Here is some code which will solve your problem:

Map<Integer, List<Node>> mapOfLinkedList = new HashMap<Integer, LinkedList<Node>>();

void addNode(Node root, int level) {
    List levelList = mapOfLinkedList.get(level);  // get List for current level
    if (levelList == null) {
        levelList = new LinkedList<Node>();
    }
    levelList.add(root);                          // add Node to the current level

    if (root.left != null) {                      // recursive left call
        addNode(root.left, level+1);
    }
    if (root.right != null) {                     // recursive right call
        addNode(root.right, level+1);
    }

    return;
}

Usage:

Node root = new Node();  // populate your tree here
addNode(root, 1);        // make initial call to recursive method here