Tree traversal in Clojure

Question

Consider a tree, which is defined by the following recursive definition:

a tree should be a vector of two elements: The first one is a number, the second one is either a list of trees or nil.

The following clojure data structure would be an example:

(def tree '[9 ([4 nil]
               [6 nil]
               [2 ([55 nil]
                   [22 nil]
                   [3 ([5 nil])])]
               [67 ([44 nil])])])

This structure should be transformed into a list of all possible downwards connections, that can be made from any node to its childs. The connections should be represented as vectors containing the value of the parent node followed by the value of the child node. The order is not important:

(def result '([9 4]
              [9 6]
              [9 2]
              [2 55]
              [2 22]
              [2 3]
              [3 5]
              [9 67]
              [67 44])

I came up with this solution:

(defn get-connections [[x xs]]
  (concat (map #(vector x (first %)) xs)
          (mapcat get-connections xs)))

And, indeed:

(= (sort result)
   (sort (get-connections tree)))
;; true

However, are there better ways to do so with just plain clojure? In the approach, I'm traversing each node's childs twice, this should be avoided. In this particular case, tail-recursion is not necessary, so a simple recursive version would be ok.

Moreover, I'd be interested which higher level abstractions could be used for solving this. What about Zippers or Clojure/Walk? And finally: Which of those techniques would be available in ClojureScript as well?

leetwinski leetwinski · Accepted Answer · 2016-07-26T22:19:35

you could try combination of list comprehension + tree-seq:

user> (for [[value children] (tree-seq coll? second tree)
            [child-value] children]
        [value child-value])

;;=> ([9 4] [9 6] [9 2] [9 67] [2 55] [2 22] [2 3] [3 5] [67 44])

this should be available in cljs.

as far as i know, both zippers and clojure.walk are available in clojurescript, but in fact you don't need them for this trivial task. I guess tree-seq is rather idiomatic.

What about the double traversal, you could easily rearrange it into a single one like this:

(defn get-connections [[x xs]]
  (mapcat #(cons [x (first %)] (get-connections %)) xs))

user> (get-connections tree)
;;=> ([9 4] [9 6] [9 2] [2 55] [2 22] [2 3] [3 5] [9 67] [67 44])

then you could add laziness, to make this solution truly idiomatic:

(defn get-connections [[x xs]]
  (mapcat #(lazy-seq (cons [x (first %)] (get-connections %))) xs))

Tree traversal in Clojure

1 Answers