Is there a way to get the list of all the subsequents child of given parent from the map?

Question

    public static Map<String, List<String>> childParentMap = new HashMap<>();


    public static List<String> immediateParents(String key) {
        return childParentMap.get(key);
    }

    public static List<String> getAllParents(String key, List<String> allParents) {

        List<String> immediateParents = childParentMap.get(key);

        if (immediateParents == null || immediateParents.isEmpty()) {
            return new ArrayList<>();
        }
        for (String parent : immediateParents) {

            List<String> list = getAllParents(parent, allParents);
            allParents.addAll(list);
            allParents.add(parent);

        }
        allParents.add(key);
        return allParents;

    }


    public static void main(String[] args) {
        System.out.println("helloo world");
        childParentMap.put("fc", Arrays.asList("x", "y"));
        childParentMap.put("x", Arrays.asList("m", "n"));

        String key = "fc";  // get all parents of fc child.
        List<String> res = getAllParents(key, new ArrayList<>());
        System.out.println(res);


    }
}

Here for the given key(say parent "fc") I want to get all its values(say children which will x,y,m and n). Reason is fc have children x and y, but x also have children m and n. so for fc all the hierarchal children's will be x,y,m and n.

I have given the try, but while running the above code i am getting the duplicates also, I tried to debug but not able to get it. This is what i am getting the output [m, n, x, m, n, x, x, y, fc] which have duplicates.

I have tried writing the code with recursion but the output seems to have duplicates. While the correct output should be [m, n, x, y];

Answer 1

Don't complicate things unnecessarily. Find the direct values and iterate over them and check if your map has this as keys, if so make a recursive call. Here are two approaches one with plain loops and one with streams:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Stream;

public class Example {

    public static Map<String, List<String>> childParentMap = new HashMap<>();

    public static void main(String[] args) {

        childParentMap.put("fc", Arrays.asList("x", "y"));
        childParentMap.put("x", Arrays.asList("m", "n"));

        String key = "fc";  // get all parents of fc child.
        List<String> res = getAllParentsStream(key);
        System.out.println(res);

        List<String> res2 = getAllParentsForLoop(key);
        System.out.println(res2);

    }

    public static List<String> getAllParentsForLoop(String key) {
        List<String> parents = new ArrayList<>();
        if (childParentMap.containsKey(key)) {
            List<String> directParents = childParentMap.get(key);
            parents.addAll(directParents);

            for (String parent : directParents) {
                if (childParentMap.containsKey(parent)) {
                    parents.addAll(getAllParentsForLoop(parent));
                }
            }
        }
        return parents;
    }

    public static List<String> getAllParentsStream(String key) {
        return Stream.concat(
                             childParentMap.get(key).stream(),
                             childParentMap.get(key).stream()
                                           .flatMap(ch -> childParentMap.containsKey(ch) ? 
                                                          getAllParentsStream(ch).stream() : 
                                                          Stream.empty()))
                     .toList();
    }
}