How to convert seq to tree

Question

I have seq of such cards as, for example, coll. I want to arrange it on a tree. Each card has a key named: parent, which is: parent id. Any tips on how I can do this?

(def coll [{:id 1} {:id 2 :parent 1} {:id 3 :parent 1} {:id 4 :parent 2} {:id 5 :parent 4} {:id 6 :parent 5} {:id 7 :parent 5} {:id 8 :parent 5} {:id 9 :parent 7}]) 

Answer 1

If he goes like a tree ...

 (require '[clojure.zip :as z]) (defn create-zipper [s] (let [g (group-by :parent s)] (z/zipper g #(map :id (g %)) nil (-> nil g first :id)))) (def t (create-zipper coll)) ; using the coll defined in the OP (-> tz/root) ;=> 1 (-> tz/children) ;=> (2 3) (-> tz/next z/children) ;=> (4) 

Note that you can save the format of the source nodes (and not just return the identifier numbers) by using #(g (% :id)) as children and (first (g nil)) as the root.

You can use post-order traversal to create another tree view if necessary.

Answer 2

Here's a small solution that uses understanding of consistency. Hopefully it will be readable, but it definitely won’t win any performance awards as it will re-filter the list at each recursion level. I suppose that an incredibly effective solution based on reduction is possible, but I still get the opportunity to write them - I hope someone else will publish one :).

Note. I returned the entire map for each node, since I was not sure exactly how you wanted your tree to look ...

 (defn make-tree ([coll] (let [root (first (remove :parent coll))] {:node root :children (make-tree root coll)})) ([root coll] (for [x coll :when (= (:parent x) (:id root))] {:node x :children (make-tree x coll)}))) (pprint (make-tree coll)) {:node {:id 1}, :children ({:node {:parent 1, :id 2}, :children ({:node {:parent 2, :id 4}, :children ({:node {:parent 4, :id 5}, :children ({:node {:parent 5, :id 6}, :children ()} {:node {:parent 5, :id 7}, :children ({:node {:parent 7, :id 9}, :children ()})} {:node {:parent 5, :id 8}, :children ()})})})} {:node {:parent 1, :id 3}, :children ()})}