paths from root to leaf of a binary tree in clojure

Question

I'm trying to implement a recursive function that can find all the paths from the root to the leaves in a binary tree in clojure, but I'm stuck. Here's an example of what the tree looks like: binary tree

I've been trying to find inspiration from the implementation in java https://www.geeksforgeeks.org/given-a-binary-tree-print-all-root-to-leaf-paths/ , but I still don't know how to write a similar function in clojure. This is the helper function I've written so far.

 (defn helper

[T P i]

(if (not (= nil T))
    (do (def P (conj P (T :value)))
        P
    )
)

(if (isbranch? T)
    (cond
       (and (not (= nil (T :left))) (= nil (T :right))) (helper (T :left) P (+ i 1))
       (and (not (= nil (T :right))) (= nil (T :left))) (helper (T :left) P (+ i 1))
       :else (do (helper (T :left) P (+ i 1)) (helper (T :left) P (+ i 1)))
    )
    (print P)
))

Could someone explain where I should start?

Answer 1

I assume that the tree is represented like this by reading the code in the question:

(def input {:value 10
            :left {:value 8 :left {:value 3} :right {:value 5}}
            :right {:value 2 :left {:value 2}}})

Apart from that, it is not clear to me how the code provided in the question is supposed to work.

Here is recursive solution that I suggest:

(defn- all-paths-recursive-sub [dst path {:keys [value left right]}]
  (let [children (remove nil? [left right])
        path (conj path value)]
    (if (empty? children)
      (conj dst path)
      (reduce (fn [dst subtree] (all-paths-recursive-sub dst path subtree))
              dst
              children))))

(defn all-paths-recursive [tree]
  (all-paths-recursive-sub [] [] tree))

(all-paths-recursive input)
;; => [[10 8 3] [10 8 5] [10 2 2]]

and here is an iterative solution:

(defn all-paths-iterative [tree]
  (loop [stack [[[] tree]]
         result []]
    (if (empty? stack)
      result
      (let [[[path {:keys [value left right]}] & stack] stack
            children (remove nil? [left right])
            path (conj path value)]
        (if (empty? children)
          (recur stack (conj result path))
          (recur (into stack (map (partial vector path)) children) result))))))

(all-paths-iterative input)
;; => [[10 2 2] [10 8 5] [10 8 3]]