A quick example to spec a tree-like data structure consisting of leafs, recursive nodes, and an empty list

spec-tree-example.clj

(ns spec-intro.core
  (:require
   [clojure.spec.alpha :as s]))


(s/def ::tree (s/or
               :empty (s/and coll? empty?)
               :node (s/cat :left (s/? ::tree)
                            :right (s/? ::tree))
               :leaf (complement coll?)))

(def tree [0 [1 [2 [3 []]]]])

[(s/conform ::tree tree)
 (s/conform ::tree [1 0])
 (s/conform ::tree [])
 (s/conform ::tree 1)]

;; =>

[[:node
  {:left [:leaf 0],
   :right
   [:node
    {:left [:leaf 1],
     :right
     [:node
      {:left [:leaf 2],
       :right [:node {:left [:leaf 3], :right [:empty []]}]}]}]}]
 [:node {:left [:leaf 1], :right [:leaf 0]}]
 [:empty []]
 [:leaf 1]]