how to transform a seq into a tree

Question

I have a seq of maps such as the coll below. I want to arrange it in a tree. Each map has a key named :parent which is the :id of the parent. Any hints on how can I do it ?

(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 it walks 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

(-> t z/root)
;=> 1

(-> t z/children)
;=> (2 3)

(-> t z/next z/children)
;=> (4)

Note that you may preserve the format of the original nodes (rather than just returning id numbers) by using #(g (% :id)) as the children and (first (g nil)) as the root.

You can use post-order traversal to build up another representation of the tree if desired.