A vector of maps into a tree

Question

I have a collection that has the following structure [{:a 0} {:b 1} {:c 1} {:d 2} {:e 3} {:f 2}]. Basically, it is a tree, where an element of the vector is a node. What the number signify is the parent-child relationship. So, the element {:a 0} is the master parent (has no parents), while {:b 1}, {:c 1} are childs of {:a 0}. Also, {:d 2} is a child of {:c 1}.

What I want is to construct a list or a vector (doesn't matter at this point) that has the following structure: [{:a {:b nil :c {:d {:e nil} :f nil}}}].

How can this be achieved?

How do you know whether d is a child of b or c? (Same question for f) — jas
Honestly, I haven't. However, what I was thinking of is to have function that looks into each element, and see if the previous element has a value that is less by one. If so it is its parent. If not then I look into the one that is 2-steps previous, and so forth. But I couldn't build such a function. — Hassan Shahin
@jas. In the structure that I am interested in, d is a child of c, as it is the nearest element to d. — Hassan Shahin
That makes sense --- I can see now that it's building the tree following a depth first path. — jas

Olim Saidov Olim Saidov · Accepted Answer · 2018-07-24T04:02:10

This should work:

(fn [xs]
  (loop [[x & rs :as xs] xs
         m   {}
         lvl {}]
    (if (seq xs)
      (let [[k l] (first x)
            p (conj (lvl (dec l) []) k)]
        (recur
          rs
          (assoc-in m p nil)
          (assoc lvl l p)))
      m)))

As @jas mentioned we can't rely on key-order of map, so here we use lvl map to keep last seen element's path per level.

A vector of maps into a tree

1 Answers