Stumped with functional breadth-first tree traversal in Clojure?

20
votes

Say I have a tree defined as per the recommendation in this post, although it's a vector in my case, which hopefully shouldn't matter (they're vectors in Programming Clojure book):

(def tree [1 [[2 [4] [5]] [3 [6]]]])

which should be something like:

      1
     / \
    2   3
   / \  |
  4   5 6

Now, I'd like to do a breadth-first traversal of the tree without any of the traditional means such as the queue, and instead use exclusively the stack to pass information around. I know this isn't the easiest route, but I'm doing it mostly as exercise. Also at this point I'm not planning to return a collection (I'll figure that out afterwards as exercise) but instead just print out the nodes as I travel through them.

My current solution (just starting out with Clojure, be nice):

(defn breadth-recur
  [queue]
  (if (empty? queue)
    (println "Done!")
    (let [collections (first (filter coll? queue))]
      (do
        ; print out nodes on the current level, they will not be wrapped'
        ; in a [] vector and thus coll? will return false
        (doseq [node queue] (if (not (coll? node)) (println node)))
        (recur (reduce conj (first collections) (rest collections)))))))

The last line is not working as intended and I'm stumped about how to fix it. I know exactly what I want: I need to peel each layer of vectors and then concatenate the results to pass into recur.

The issue I'm seeing is mostly a:

IllegalArgumentException Don't know how to create ISeq from: java.lang.Long

Basically conj doesn't like appending a vector to a long, and if I swap conj for concat, then I fail when one of the two items I'm concatenating isn't a vector. Both conj and concat fail when facing:

[2 [4] [5] [3 [6]]]

I feel like I'm missing a really basic operation here that would work both on vectors and primitives in both positions.

Any suggestions?

Edit 1:

The tree should actually be (thanks Joost!):

(def tree [1 [2 [4] [5]] [3 [6]]])

However we still haven't found a breadth-first solution.

4
algorithmclojurefunctional-programming
Did you have a look at the source of the functions in clojure.walk or the function tree-seq? They implement tree traversal and might be interesting to you. - Gert
@Gert: It's my impression that all of those are depth-first, correct? I also considered zippers, but then my brain started melting at the thought. - Alexandr Kurilin
Ah yes, clojure.walk does depth-first traversal; I missed the breadth-first requirement in your post, oops! - Gert

4 Answers

23
votes

Since apparently there is still no breadth-first solution posted, here is a simple algorithm, implemented first eagerly, and then transformed to be lazy:

(defn bfs-eager [tree]
  (loop [ret [], queue (conj clojure.lang.PersistentQueue/EMPTY tree)]
    (if (seq queue)
      (let [[node & children] (peek queue)]
        (recur (conj ret node) (into (pop queue) children)))
      ret)))

(defn bfs-lazy [tree]
  ((fn step [queue]
     (lazy-seq
      (when (seq queue)
        (let [[node & children] (peek queue)]
          (cons node
                (step (into (pop queue) children)))))))
   (conj clojure.lang.PersistentQueue/EMPTY tree)))
13
votes

Your tree data is incorrect. It should be [1 [2 [4] [5]] [3 [6]]]

Also, you're mixing the tree traversal with printing and building up a result. Things get simpler if you concentrate on doing the hard part separately:

(def tree [1 [2 [4] [5]] [3 [6]]])

NOTE THIS IS DEPTH-FIRST. SEE BELOW

(defn bf "return elements in tree, breath-first"
   [[el left right]] ;; a tree is a seq of one element,
                     ;; followed by left and right child trees
   (if el
     (concat [el] (bf left) (bf right))))

(bf tree)
=> (1 2 4 5 3 6)

CORRECT VERSION

(defn bf [& roots] 
   (if (seq roots) 
       (concat (map first roots) ;; values in roots
               (apply bf (mapcat rest roots))))) ;; recursively for children

(bf tree)
=> (1 2 3 4 5 6)
1
votes

This might help, I was creating an algorithm to evaluate if a tree is symmetric and used a breadth-first traversal:

(defn node-values [nodes]
    (map first nodes))

(defn node-children [nodes]
  (mapcat next nodes))

(defn depth-traversal [nodes]
    (if (not (empty? nodes))
        (cons (node-values nodes) (depth-traversal (node-children nodes)))))

(defn tree-symmetric? [tree]
    (every?
        (fn [depth] (= depth (reverse depth)))
        (depth-traversal (list tree))))

(def tree '(1 (2 (3) (4)) (2 (4) (3))))
(node-values (list tree)) ; (1)
(node-children (list tree)) ; ((2 (3) (4)) (2 (4) (3)))
(depth-traversal (list tree)) ; ((1) (2 2) (3 4 4 3))
(tree-symmetric? tree) ; true
0
votes

many combinations of reduceand conj can be replaced with single into call in the case above with reduce you may need to pass an initial empty vector to reduce to get make conjunction happy.