How to traverse a tree in Clojure while collecting

Question

I want to create a function that collects the value from each node in a binary tree. In the ClojureDocs, I found several functions for traversing a tree/graph, such as tree-seq, prewalk, and postwalk.

https://clojuredocs.org/clojure.core/tree-seq

https://clojuredocs.org/clojure.walk/prewalk

https://clojuredocs.org/clojure.walk/postwalk

Can any of these be used to accumulate the value of nodes traversed? As a Clojure newby, I don't see how to do it. If you know how (in Clojure or similar Lispy language), please show me. Ideally, your answer will be understandable by a Clojure newby;-)

My binary tree is represented with nodes like this: (value left-child right-child). For example:

( 2 (7 nil nil) (88 (5 nil nil) nil) )

From this example, I'd like the function to return (2 7 88 5).

NOTE: The traversal method isn't important. I just want to learn a technique for collecting node values.

Answer 1

Well, tree-seq will give you the node sequence (of a depth first walk). You can then do any other transformation on it, including (map some-value-extractor-fn (tree-seq ... to get the values in each node. You just need to pick a tree representation and appropriate functions for that representation so tree-seq can know what is an internal node and what its children are. For instance, using your definition of the tree as a nested list:

Nested list tree

The nodes where our tree could branch are lists, which we can identify using list?.Their children are the values following the first, i.e. their rest. So we can define the tree-seq using only standard functions:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest))

but this has a bit of garbage - each nil appears as a member of the seq, each value we're interested in appears both in its list node and as a member in itself and so on. We can clean this up with a filter or remove - for instance we can discard all the leaf values and take only internal nodes:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest)
     (filter list?))
;;=> ((2 (7 nil nil) (88 (5 nil nil) nil)) (7 nil nil) (88 (5 nil nil) nil) (5 nil nil))

and then just map first over those:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest)
     (filter list?)
     (map first)) ;;=>(2 7 88 5)

Alternatively we could try to discard internal and nil nodes of the tree, taking only leaves with a value:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? seq)
     (remove (some-fn list? nil?))) ;;=>(2 7 88 5)

Note that in this strategy I had to use seq rather than rest, as I want the first value in a list to also be a child of that node. (some-fn list? nil?) is a bit of higher order functions - it builds a function that checks if the input satisfies either of the predicates list? or nil? (or both).

Nested map tree

If you want a maybe more general tree definition, where each node can contain multiple values plus a variable number of children, you can define your tree as nested maps: {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]}

In this case, looking at only the maps as nodes is generally simplest. Our possibly branching nodes are maps - check for that with map?. We stored their children in the key :children, which is a keyword and so is also a function. We use that function to get the children.

(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]} 
     (tree-seq map? :children)) 
;;=> ({:value 2, :children [{:value 7} {:value 88, :children [{:value 5}]}]} {:value 7} {:value 88, :children [{:value 5}]} {:value 5})

and then you just need to map over the nodes to get the data you want out of them:

(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}] } 
     (tree-seq map? :children)
     (map :value)) ;;=> (2 7 88 5)

Answer 2

for accumulating node values of a tree, i have a non-functional solution:

user> (def a (atom 0))
#'user/a
user> (dorun (clojure.walk/postwalk #(when (number? %) (swap! a (partial + %))) '( 2 (7 nil nil) (88 (5 nil nil) nil))))
nil
user> @a
102