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.
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)))
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)
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With