CODEWITHSUNDEEP
clojurefunctional-programminglisp
expojure
expojure

Reputation: 39

Growing my Clojure Tree

I am hoping someone can help, so I'm taking the leap from OOP to Functional programming and it's a bit daunting! I am trying to write a function that will return to me the total sum of numbers in a sub-tree, but I only want to return the sub-tree which is the greater value. If that makes sense? I have written a function that returns the total trees maxsum but want to extend

For example:

         []
         |
    ---------
    |        |
    []      []    
   / \      /\
  1   []   3  []    <--biggest sub-tree
      /\      /\
     3  2    8  8

(defn is-tree [tr]
  (and (seq? tr) (not (empty? tr))))

(defn tree-total [tree]
  (cond
    (number? tree) tree

    (is-tree tree)
    (+ (tree-total (first tree))
      (tree-total (rest tree)))

    :else 0
    ))

This is as far as I have came, which gives me a total of the whole thing, but I cannot implement it to only do the math on the sub-tree... Can anyone help me out?

I half had a solution but it didn't get me anywhere which was this...

(let [l-s-tree (myhelperfunc? (first tree))
      r-s-tree (myhelperfunc? (last tree))

      lt (tree-sum (first tree))
      rt (tree-sum (last tree))

      both (+ lt rt)]

But I couldn't implement this into my current function, I'm totally at a loss as to extend it. Can anyone help a hand?

Upvotes: 1

Views: 110

Answers (1)

Magos
Magos

Reputation: 3014

Recursive functions over trees are always a bit of a bother, especially when you're trying to test them out on the REPL. Here's my attempt:

(defn max-subtree-sum [x]
  (if (coll? x) ;;Is this an internal node?
    (if (every? number? x) 
      ;;If every child is a number, we should sum them.
      (apply + x)
      ;;otherwise recur once for each child and take the max
      (apply max (map max-subtree-sum x)))
     x))

(max-subtree-sum [[1 [3 2]] [3 [8 8]]])
;; => 16
(max-subtree-sum '((1 (3 24)) (3 (8 8))));; Or with lists
;; => 27

I used coll? to check for tree-ness because in your diagram it looked like your internal nodes were vectors, and as it turns out those are not seq? I've just assumed that anything that isn't a collection is a number - if you have a more mixed-data tree you should be able to handle that by replacing the outer if with a cond and a final :else 0 clause like in your attempt.

The major addition here is looking at the children of internal nodes before deciding what to do with them. If they're all numbers then we're making a sum. If they're not then we're an entirely internal node and need to take the max instead. You can do both using apply (basically, (apply f [x y z]) is (f x y z) - it plumbs collections into functions as individual arguments), once we've used map to recursively get the max-subtree-sums of subtree children.

Upvotes: 1

Related Questions