tree-seq

;; Each node is a number or a seq, 
;; so branch?==seq? and children==identity
;; 
;;     .
;;    / \
;;   .   .
;;  /|\  |
;; 1 2 . 4
;;     |  
;;     3
;;
;; ... each sub-tree is serialized in depth-first order
(tree-seq seq? identity '((1 2 (3)) (4)))

;;=> (((1 2 (3)) (4)) 
;;     (1 2 (3)) 
;;        1 
;;        2 
;;        (3) 
;;            3 
;;     (4) 
;;        4)

(tree-seq map? #(interleave (keys %) (vals %)) {:a 1 :b {:c 3 :d 4 :e {:f 6 :g 7}}})
;;=> ({:a 1, :b {:c 3, :d 4, :e {:f 6, :g 7}}} 
;;     :a 1 :b {:c 3, :d 4, :e {:f 6, :g 7}} 
;;              :c 3 :d 4 :e {:f 6, :g 7}  
;;                            :f 6 :g 7)

;; Each node is a (node-root child1 child2 ...),
;; so branch?==next and children==rest
;;
;;     A
;;    / \
;;   B   C
;;  / \  |
;; D   E F
;;
(map first (tree-seq next rest '(:A (:B (:D) (:E)) (:C (:F)))))
;;=> (:A :B :D :E :C :F)

;; The previous example seems to be a flatten function,
;; where every node's value is added to the returned sequence
;; as it is visited in a depth first search.
;; That is not the case as the following example illustrates: 
;;      *
;;     / \
;;    *   4
;;   /|\
;;  1 2 *
;;      |
;;      3
(map first (tree-seq next rest '((1 2 (3)) (4))))
;;=> ((1 2 (3)) 4)

;; For a proper 'flatten' function see below.

;; The nodes are filtered based on their collection type, 
;; here they must be a list.
(tree-seq seq? seq [[1 2 [3]] [4]])
;;=> ([[1 2 [3]] [4]])

;; notice the difference between seq? and sequential?
(tree-seq sequential? seq [[1 2 [3]] [4]])
;;=> ([[1 2 [3]] [4]] [1 2 [3]] 1 2 [3] 3 [4] 4)

;; If the nodes in the tree are a specific type of collection...
;; a vector
(tree-seq vector? seq [[1 2 [3]] [4]])
([[1 2 [3]] [4]] [1 2 [3]] 1 2 [3] 3 [4] 4)

;; ... or a list
(tree-seq seq? seq '((1 2 (3)) (4)))
(((1 2 (3)) (4)) (1 2 (3)) 1 2 (3) 3 (4) 4)

;; Use tree-seq to recursively find all files 
;; given a root directory (here for didactic purposes. See file-seq)
(let [directory (clojure.java.io/file "/path/to/directory/")
      dir? #(.isDirectory %)]
    ;we want only files, therefore filter items that are not directories.
    (filter (comp not dir?) 
          (tree-seq dir? #(.listFiles %) directory)))

(def t '((1 2 (3)) (4)))
;;=> #'user/t

;; Here the tree-seq uses 'sequential?' as the 'branch?' predicate.
;; This causes the 'children' function to run for any collection.
;; The 'seq' ('children') function recurses on all items in the collection.
;; This results in a sequence of sub-trees, rooted at each node.
(tree-seq sequential? seq t)
;;=> (((1 2 (3)) (4))
;;    (1 2 (3)) 1 2 
;;    (3) 3 (4) 4)

;; (The following example is from 4Clojure)
;; It returns the leaves of a tree as a sequence.
;; 
(defn flatten [x]
  (filter (complement sequential?)
          (rest (tree-seq sequential? seq x))))
(flatten t)
;;=> (1 2 3 4)

(tree-seq seq? identity '(1 2 (3 (4))))
;; ((1 2 (3 (4))) 1 2 (3 (4)) 3 (4) 4)

;; It's same as ...
(tree-seq seq? seq '(1 2 (3 (4))))
(tree-seq sequential? seq '(1 2 (3 (4))))
;; ((1 2 (3 (4))) 1 2 (3 (4)) 3 (4) 4)

;; This processing ...
(sequential? '(1 2 (3 (4)))) ;; returns true ... -> (1 2 (3 (4))) <--- !!!
(sequential? 1)              ;; returns false ... -> 1
(sequential? 2)              ;; returns false ... -> 2
(sequential? '(3 (4))        ;; returns true  ... -> (3 (4))     <--- !!! 
(sequential? 3)              ;; returns false ... -> 3
(sequential? '(4))           ;; returns true  ... -> (4)         <--- !!!
(sequential? 4)              ;; return false  ... -> 4

;; so, #tree-seq returns...
;; ((1 2 (3 (4))) 1 2 (3 (4)) 3 (4) 4)

;; When traversing a map tree, it's sometimes useful to have a back-reference
;; to the parent.  This tree-seq variant provides that.

(defn tree-seq-adding-parent
  "Like tree-seq, but takes in a tree of maps and a unique :parent key to each map."
  [branch? children root]
  (let [walk (fn walk [parent node]
               (lazy-seq
                (cons (assoc node :parent parent)
                 (when (branch? node)
                   (mapcat (partial walk node) (children node))))))]
    (walk nil root)))

(def map-tree
  {:name "root"
   :children [{:name "child1"
               :children [{:name "grandchild1"}
                          {:name "grandchild2"}]}
              {:name "child2"}]})

(tree-seq-adding-parent associative? :children map-tree)
;; =>
;; ({:name "root",
;;   :children
;;   [{:name "child1",
;;     :children [{:name "grandchild1"} {:name "grandchild2"}]}
;;    {:name "child2"}],
;;   :parent nil
;;  {:name "child1",
;;   :children [{:name "grandchild1"} {:name "grandchild2"}],
;;   :parent
;;   {:name "root",
;;    :children
;;    [{:name "child1",
;;      :children [{:name "grandchild1"} {:name "grandchild2"}]}
;;     {:name "child2"}]}}
;;  {:name "grandchild1",
;;   :parent
;;   {:name "child1",
;;    :children [{:name "grandchild1"} {:name "grandchild2"}]}}
;;  {:name "grandchild2",
;;   :parent
;;   {:name "child1",
;;    :children [{:name "grandchild1"} {:name "grandchild2"}]}}
;;  {:name "child2",
;;   :parent
;;   {:name "root",
;;    :children
;;    [{:name "child1",
;;      :children [{:name "grandchild1"} {:name "grandchild2"}]}
;;     {:name "child2"}]}})

;; Tree-seq uses depth-first search (DFS), pre-order traversal, to explore the 
;; tree. 
;;
;;     1
;;    / \
;;   2   3
;;   |  
;;   4
;;   |
;;   5

(let [tree {:value 1 
            :children [{:value    2
                        :children [{:value    4
                                    :children [{:value 5}]}]}
                       {:value 3}]}]
     (map :value
       (tree-seq
         #(contains? % :children) ;branch?
         #(get % :children) ;children
         tree)))

=> (1 2 4 5 3)