CODEWITHSUNDEEP
clojure
adapt-dev
adapt-dev

Reputation: 1768

In a tree, how do I find paths to tree nodes that have children with leaves?

Basically, I am trying to implement this algorithm, though maybe there's a better way to go about it.

non-functional pseudo code: 

def find_paths(node):
    for child in node.children:
       if child.children.len() == 0
          child_with_leaf = true
    if child_with_leaf
       record path to node
    else
       for child in node.children
           find_paths(child)

For example: 

:root
  |- :a
  |   +- :x
  |       |- :y
  |       |   +- :t
  |       |       +- :l2
  |       +- :z
  |          +- :l3
  +- :b
      +- :c
          |- :d
          |   +- :l4
          +- :e
              +- :l5

The result would be:

[[:root :a]
 [:root :b :c]]

Here is my crack at it in clojure:

(defn atleast-one?
  [pred coll]
  (not (nil? (some pred coll))))

; updated with erdos's answer
(defn children-have-leaves?
  [loc]
  (some->> loc
           (iterate z/children)
           (take-while z/branch?)
           (atleast-one? (comp not empty? z/children))))

(defn find-paths
  [tree]
  (loop [loc (z/vector-zip tree)
         ans nil]
    (if (z/end? loc)
      ans
      (recur (z/next loc)
             (cond->> ans
                      (children-have-leaves? loc)
                      (cons (->> loc z/down z/path (map z/node)))))))
  )

(def test-data2
  [:root [:a [:x [:y [:t [:l2]]] [:z [:l3]]]] [:b [:c [:d [:l4]] [:e [:l5]]]]]
  )

Update: fixed the crash with erdos' answer below, but I think there's still a problem with my code since this prints every path and not the desired ones.

Upvotes: 0

Views: 288

Answers (3)

rmcv
rmcv

Reputation: 1976

I assume you have referenced my previous answer related to zipper. But please note that my previous answer uses vector-zip as is and hence you have to navigate it like a vector-zip - which you may have to wrap your head around how the two cursors work. To simplify the navigation, I suggest you create your own zipper for your tree structure. I.e.

(defn my-zipper [root]
  (z/zipper ;; branch?
            (fn [x]
              (when (vector? x)
                (let [[n & xs] x] (and n (-> xs count zero? not)))))
            ;; children
            (fn [[n & xs]] xs)
            ;; make-node
            (fn [[n & _] xs] [n xs])
            root))

then the solution will be similar to my other answer:

(def test-data2
  [:root 
   [:a 
    [:x 
     [:y 
      [:t [:l2]]] 
     [:z [:l3]]]] 
   [:b 
    [:c 
     [:d [:l4]] 
     [:e [:l5]]]]])

(->> test-data2
     my-zipper
     (iterate z/next)
     (take-while (complement z/end?))
     (filter (comp children-with-leaves? z/node))
     (map #(->> % z/path (map z/node)))
     set)
;; => #{(:root :a :x) (:root :a :x :y) (:root :b :c)}

where the main logic is simplified to:

(defn children-with-leaves? [[_ & children]]
  (some (fn [[c & xs]] (nil? xs)) children))

Upvotes: 2

Alan Thompson
Alan Thompson

Reputation: 29958

If you want to process tree-like data structures, I would highly recommend the tupelo.forest library.

I don't understand your goal, though. Nodes :a and :c in your example are not equally distant from the closest leaf.

Actually, I just noticed that the tree in your example is different than the tree in your code attempt. Could you please update the question to make them consistent?

Here is an example of how you could do it:

(dotest ; find the grandparent of each leaf
  (hid-count-reset)
  (with-forest (new-forest)
    (let [data              [:root
                             [:a
                              [:x
                               [:y [:t [:l2]]]
                               [:z [:l3]]]]
                             [:b [:c
                                  [:d [:l4]]
                                  [:e [:l5]]]]]
          root-hid          (add-tree-hiccup data)
          leaf-paths        (find-paths-with root-hid [:** :*] leaf-path?)
          grandparent-paths (mapv #(drop-last 2 %) leaf-paths)
          grandparent-tags  (set
                              (forv [path grandparent-paths]
                                (let [path-tags (it-> path
                                                  (mapv #(hid->node %) it)
                                                  (mapv #(grab :tag %) it))]
                                  path-tags)))]
      (is= (format-paths leaf-paths)
        [[{:tag :root} [{:tag :a} [{:tag :x} [{:tag :y} [{:tag :t} [{:tag :l2}]]]]]]
         [{:tag :root} [{:tag :a} [{:tag :x} [{:tag :z} [{:tag :l3}]]]]]
         [{:tag :root} [{:tag :b} [{:tag :c} [{:tag :d} [{:tag :l4}]]]]]
         [{:tag :root} [{:tag :b} [{:tag :c} [{:tag :e} [{:tag :l5}]]]]]])
      (is= grandparent-tags
          #{[:root :a :x] 
            [:root :a :x :y] 
            [:root :b :c]} ))))

Upvotes: 0

erdos
erdos

Reputation: 3528

The exception comes from your children-have-leaves? function.

The (not (empty? z/children)) expression fails, because z/children is a function, however, empty? must be invoked on a collection.

What you need is a predicate that returns true if a node has children, like: (fn [x] (not (empty? (z/children x)))) or shorter: (comp not empty? z/children)

The correct implementation:

(defn children-have-leaves?
  [loc]
  (some->> loc
           (iterate z/children)
           (take-while z/branch?)
           (atleast-one? (comp not empty? z/children))))

Upvotes: 2

Related Questions