clojure.core/tree-seq

View this page on ClojureDocs

Type: function Added: Clojure 1.0 Examples: 10 Runnable: 6

([branch? children root])

Returns a lazy sequence of the nodes in a tree, via a depth-first walk. branch? must be a fn of one arg that returns true if passed a node that can have children (but may not). children must be a fn of one arg that returns a sequence of the children. Will only be called on nodes for which branch? returns true. Root is the root node of the tree.

Examples

by devn on 2010-08-02 ▶

;; 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)

by patazj on 2011-11-16 ▶

(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)

by algal on 2011-11-21 ▶

;; 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)

by gregginca on 2012-04-10 ▶

;; 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.

by devn on 2012-04-26 . May have evaluation errors. ▶

;; 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)

by shark8me on 2015-02-05 . May have evaluation errors. ▶

;; 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)))

by phreed on 2016-02-03 ▶

(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)

by MokkeMeguru on 2017-08-28 . May have evaluation errors. ▶

(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)

by kovasap on 2022-05-08 ▶

;; 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"}]}})

by jacobmendoza on 2023-10-27 . May have evaluation errors. ▶

;; 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)

Note by phreed

The 'branch?' and 'children' functions perform different types of filtering. The 'branch?' function examines a node and determines whether there are children that need to be included in the processing. The 'children' function selects (or generates) the children to be included in the returned sequence.

Note by lostdiaspora

Example 5 has for the second example (tree-seq seq? seq [[1 2 [3]] [4]]) when it should be (tree-seq sequential? seq [[1 2 [3]] [4]])

See also

• clojure.walk/walk
• clojure.core/file-seq (0)

---

Content from the matching ClojureDocs page, with authors credited on each contribution.