Tree height (Lisp)

From LiteratePrograms

Jump to: navigation, search

Trees are commonly represented as nested lists in Lisp. The height or depth of such a tree the maximum nesting-depth of that nested list. Use the code below to compute that recursively.

<<tree-height>>=
(defun tree-height (tree)
  "Recursively compute the depth of given tree. 0 for NIL."
  (reduce #'max
    (mapcar (lambda (child) (if (listp child) (1+ (tree-height child)) 1)) tree)
    :initial-value 0))
Download code
Views