A Clojure solution to Xah Lee's programming challenge "Constructing a Tree Given Its Edges".

gistfile1.clj

(defn parent-children-map
  "Converts a vector of [child parent] edges into a map where every entry has
  the form [parent set-of-children].

  Examples:

  (parent-children-map [[0, 2], [3, 0], [1, 4], [2, 4]])
  ;=> {4 #{1 2}, 0 #{3}, 2 #{0}}

  (parent-children-map [[10 1] [1 4] [6 1] [8 6] [9 5] [2 4]
                        [3 0] [7 0] [5 2] [0 2] [11 1]])
  ;=> {2 #{0 5}, 0 #{3 7}, 5 #{9}, 6 #{8}, 4 #{1 2}, 1 #{6 10 11}}"
  [edges]
  (reduce (fn [m [child parent]]
            (update-in m [parent]
                       (fn [s] (set (conj s child)))))
          {}
          edges))

(defn get-root
  "Gets the root entry of the parent-children-map pcm."
  [pcm]
  (loop [xs pcm]
    (if (seq xs)
      (let [[p _ :as root] (first xs)]
        (if (some (fn [[_ cs]] (contains? cs p)) pcm)
          (recur (rest xs))
          root))
      (throw (RuntimeException. "There is no root!")))))

(defn make-tree
  "Returns a map representing the given sequence of edges (each edge
  represented as [child parent]) as a tree.

  Examples:

  (make-tree [[0, 2], [3, 0], [1, 4], [2, 4]])
  ;=> {4 {2 {0 {3 nil}},
          1 nil}}

  (make-tree [[10 1] [1 4] [6 1] [8 6] [9 5] [2 4]
              [3 0] [7 0] [5 2] [0 2] [11 1]])
  ;=> {4 {2 {5 {9 nil},
             0 {7 nil,
                3 nil}},
          1 {11 nil,
             10 nil,
             6 {8 nil}}}}"
  [edges]
  (let [pcm (parent-children-map edges)]
    (letfn [(build-child-trees [cs]
              (apply merge (map #(build-tree [% (pcm %)]) cs)))
            (build-tree [[root cs]]
              (if root
                {root (build-child-trees cs)}
                {}))]
      (build-tree (get-root pcm)))))

I have this data structure:
[["body" "html"]
["aside" "body"]
["menu" "aside"]
["menuitem" "menu"]
["menuitem" "menu"]
["menuitem" "menu"]
["menuitem" "menu"]
["div" "body"]
["title" "div"]
["img" "div"]
["para" "div"]
["hlink" "body"]
["form" "body"]
["input" "form"]
["btn" "form"]
["div" "form"]
["p" "div"]
["title" "div"]
["link" "div"]
["footer" "html"]
["hlink" "footer"]
["hlink" "footer"]
["hlink" "footer"]
["hlink" "footer"]]

When giving the "make-tree" function the above data structure, it produces the following result:
{"html" {"body" {"form" {"input" nil,
"div" {"img" nil, "para" nil, "p" nil, "title" nil, "link" nil},
"btn" nil},
"hlink" nil,
"div" {"img" nil, "para" nil, "p" nil, "title" nil, "link" nil},
"aside" {"menu" {"menuitem" nil}}},
"footer" {"hlink" nil}}}

Apparently this is not correct. For example the last node, the footer, should be: "footer" {"hlink" nil} {"hlink" nil} {"hlink" nil} {"hlink" nil}

On StackOverflow, I posed a question (https://stackoverflow.com/questions/51484916/a-vector-of-maps-into-a-tree/51490276?noredirect=1#comment90598511_51490276), and a gentleman there gave me a solution that produces the exact result your "make-tree" function produces.

When I apply the "parent-children-map" function to my data structure it produces a result with one "link" for the footer. This is understandable, as the function is applying the "set" function. When I remove the "set" function from the definition of "parent-children-map", the "make-tree" refuses to work, and I get the following error:
IllegalArgumentException contains? not supported on type: clojure.lang.PersistentList clojure.lang.RT.contains (RT.java:814)

So, I am wondering how can your solution be generalized to handle a case like mine?

Many thanks in advance.

Probably what I am going to say is the worst way to approach a solution provider, but ...
The solution in the stack overflow link I mentioned maintains the order of the entries, I mean the proper nesting of the entries. Here is the output of applying the function there to my "original data structure"

{"html" {"body" {"aside" {"menu" {"menuitem" nil}},
"div" {"title" nil, "img" nil, "para" nil},
"hlink" nil,
"form" {"input" nil, "btn" nil, "div" {"p" nil, "title" nil, "link" nil}}},
"footer" {"hlink" nil}}}

Which I think is different from the output of your function:
{"html" {"body" {"form" {"input" nil,
"div" {"img" nil, "para" nil, "p" nil, "title" nil, "link" nil},
"btn" nil},
"hlink" nil,
"div" {"img" nil, "para" nil, "p" nil, "title" nil, "link" nil},
"aside" {"menu" {"menuitem" nil}}},
"footer" {"hlink" nil}}}

Sorry for any inconvenience.