CODEWITHSUNDEEP
recursionclojuretree
user524824
user524824

Reputation:

Build a tree from a list of node, parent elements

I have a list of nodes, each with a parent and I want to construct a tree out of these.

(def elems '[{:node A :parent nil} {:node B :parent A} {:node C :parent A} {:node D :parent C}])
(build-tree elems)
=> (A (B) (C (D)))

Currently I have this code:

(defn root-node [elems]
  (:node (first (remove :parent elems))))

(defn children [elems root]
  (map :node (filter #(= root (:parent %)) elems)))

(defn create-sub-tree [elems root-node]
  (conj (map #(create-sub-tree elems %) (children elems root-node)) root-node))

(defn build-tree [elems]
  (create-sub-tree elems (root-node elems)))

In this solution recursion is used, but not with the loop recur syntax. Which is bad, because the code can't be optimized and a StackOverflowError is possible.
It seems that I can only use recur if I have one recursion in each step.
In the case of a tree I have a recursion for each child of a node.

I am looking for an adjusted solution that wouldn't run into this problem.
If you have a complete different solution for this problem I would love to see it.
I read a bit about zipper, perhaps this is a better way of building a tree.

Upvotes: 3

Views: 822

Answers (1)

mange
mange

Reputation: 3212

This is the solution I would go with. It is still susceptible to a StackOverflowError, but only for very "tall" trees.

(defn build-tree [elems]
  (let [vec-conj (fnil conj [])
        adj-map (reduce (fn [acc {:keys [node parent]}]
                          (update-in acc [parent] vec-conj node))
                        {} elems)
        construct-tree (fn construct-tree [node]
                         (cons node
                               (map construct-tree
                                    (get adj-map node))))
        tree (construct-tree nil)]
    (assert (= (count tree) 2) "Must only have one root node")
    (second tree)))

We can remove the StackOverflowError issue, but it's a bit of a pain to do so. Instead of processing each leaf immediately with construct-tree we could leave something else there to indicate there's more work to be done (like a zero arg function), then do another step of processing to process each of them, continually processing until there's no work left to do. It would be possible to do this in constant stack space, but unless you're expecting really tall trees it's probably unnecessary (even clojure.walk/prewalk and postwalk will overflow the stack on a tall enough tree).

Upvotes: 2

Related Questions