clojures-expressionzipper

Calculating the depth of a tree data structure - clojure


I'm trying to implement an algorithm to find the depth of a sequence expression through Clojure Zippers.

(zip/seq-zip (+ 1 (* 2 3)))

This is the way I'm interpreting a sequence to be converted into a tree data structure. Is there a direct method to calculate this through Zipper library(the depth to be calculated as 2, from the given example)?

Any suggestions would be appreciated!


Solution

  • You can use the following recursive approach:

    (defn height [s-expr]
      (if-let [sub-trees (seq (filter coll? s-expr))]
        (inc
         (apply max
                (map height sub-trees)))
        0))
    
    
    => (height '(+ 1 (* 2 3)))
    => 1
    

    Effectively the above treats collections as branches and everything else as leaves. You can replace coll? with any other branch definition (e.g. list?) that fits your needs.