Convert Map<String, ArrayList<String>> to Nested JSON

Question

So I have a Map<String, ArrayList> parentToChild and want to create basically a "Family Tree" or nested hierarchy. Below is an example of the map but there could be more children at each level e.g. (Claire could have Matt and Bruce as children):

David -> [Claire]
Claire -> [Matt]
Matt -> [Sean, Terry]

I know the root of the tree should be David for the above example and it will only have one root.

Example output

{
 "David": {
   "Claire": {
      "Matt": {
        "Sean": {},
        "Terry": {}
      }
    }
  }
}

I've tried few things but genuinely stumped.

EDIT: Code tried so far

public Set<Tree> transform(Map<String, ArrayList<String>> input) {
        Set<String> roots = new HashSet<String>(input.keySet());

        
        Map<String, Tree> map = new HashMap<String, Tree>();

        for (Map.Entry<String, ArrayList<String>> entry : input.entrySet()) {
            String key = entry.getKey();
            List<String> childKeys = entry.getValue();
            Tree tree = map.get(key);
            if (tree == null) {
                tree = new Tree(key);
                map.put(key, tree);
            }
            for (String childKey : childKeys) {
                roots.remove(childKey);
                Tree child = map.get(childKey);
                if (child == null) {
                    child = new Tree(childKey);
                    map.put(childKey, child);
                }
                tree.addChild(child);
            }
        }
        Set<Tree> res = new HashSet<Tree>(roots.size());
        for (String key : roots) {
            res.add(map.get(key));
        }
        return res;
    }

Tree class:

public class Tree {
    private String key;
    private Tree child;

    public Tree(String key){
        this.key = key;
    }

    public void addChild(Tree child){
        this.child = child;
    }
}

The issue is when I use this code the output (What is in the set after debugging/printing) I get is

David:
  Claire:
    Matt:
     Terry:

Answer 1

You could use a Map<String,Object>:

private static final Gson GSON = new GsonBuilder()
        .setPrettyPrinting()
        .create();

public static void main(String[] args) {
    Map<String, List<String>> input = new HashMap<>();
    input.put("David", Arrays.asList("Claire"));
    input.put("Claire", Arrays.asList("Matt"));
    input.put("Matt", Arrays.asList("Sean", "Terry"));
    Map<String,Object> result = new HashMap<>();
    convert(input, "David", result);
    GSON.toJson(result, System.out);
}

private static void convert(Map<String, List<String>> input, String root,
        Map<String,Object> result) {
    if (!result.containsKey(root)) {
        Map<String,Object> rootObj = new HashMap<>();
        result.put(root, rootObj);
        List<String> children = input.get(root);
        if (children != null) {
            for (String child: children) {
                convert(input, child, rootObj);
            }
        }
    }
}

Output:

{
  "David": {
    "Claire": {
      "Matt": {
        "Terry": {},
        "Sean": {}
      }
    }
  }
}

Answer 2

In the Java world you have access to Saxon 9.8 or later HE where XPath 3.1 or XQuery 3.1 or XSLT 3.0 all have support for representing your initial map as an XdmMap and processing them, for instance with XQuery:

declare namespace map = "http://www.w3.org/2005/xpath-functions/map";

declare namespace output = "http://www.w3.org/2010/xslt-xquery-serialization";

declare option output:method 'json';
declare option output:indent 'yes';

declare variable $map as map(xs:string, array(xs:string)) external := map {
    'David' : [ 'Claire' ],
    'Claire' : [ 'Matt' ],
    'Matt' : [ 'Sean', 'Terry' ]
};

declare variable $root as xs:string external := 'David';

declare function local:create-tree($map as map(xs:string, array(xs:string)), $children as xs:string*) as map(*) {
    map:merge($children ! map { . : local:create-tree($map, $map(.)) })
};

local:create-tree($map, $root)

https://xqueryfiddle.liberty-development.net/3Nzd8bV

A simple Java example to run this with Saxon 10 HE (its API documentation is at http://saxonica.com/html/documentation/using-xquery/api-query/s9api-query.html), passing a Java Map to the XQuery (inserted inline as a string but could of course be loaded from a file instead) is:

import java.util.HashMap;
import java.util.Map;
import net.sf.saxon.s9api.Processor;
import net.sf.saxon.s9api.QName;
import net.sf.saxon.s9api.SaxonApiException;
import net.sf.saxon.s9api.XQueryCompiler;
import net.sf.saxon.s9api.XQueryEvaluator;
import net.sf.saxon.s9api.XQueryExecutable;
import net.sf.saxon.s9api.XdmMap;

public class SaxonJavaMapToNestedJSONObject {


    public static void main(String[] args) throws SaxonApiException {
        
        Map<String, String[]> map = new HashMap<>();
        map.put("David", new String[] { "Claire" });
        map.put("Claire", new String[] { "Matt" });
        map.put("Matt", new String[] { "Sean", "Terry" });
        
        Processor processor = new Processor(true);
        
        XQueryCompiler compiler = processor.newXQueryCompiler();
        
        XQueryExecutable executable = compiler.compile("declare namespace map = \"http://www.w3.org/2005/xpath-functions/map\";\n" +
"\n" +
"declare namespace output = \"http://www.w3.org/2010/xslt-xquery-serialization\";\n" +
"\n" +
"declare option output:method 'json';\n" +
"declare option output:indent 'yes';\n" +
"\n" +
"declare variable $map as map(xs:string, array(xs:string)) external;\n" +
"\n" +
"declare variable $root as xs:string external := 'David';\n" +
"\n" +
"declare function local:create-tree($map as map(xs:string, array(xs:string)), $children as xs:string*) as map(*) {\n" +
"    map:merge($children ! map { . : local:create-tree($map, $map(.)) })\n" +
"};\n" +
"\n" +
"local:create-tree($map, $root)");
        
         XQueryEvaluator evaluator = executable.load();
         
         evaluator.setExternalVariable(new QName("map"), XdmMap.makeMap(map));
         
         evaluator.run(processor.newSerializer(System.out));
         
    }
    
}

Of course you could set the root variable as well from Java: evaluator.setExternalVariable(new QName("root"), new XdmAtomicValue("David"));