Representing A Tree in Clojure

What would be an idiomatic way to represent a tree in Clojure? E.g.:

     A
    / \
   B   C
  /\    \
 D  E    F

Performance is not important and the trees won't grow past 1000 elements.

Solution 1:

'(A (B (D) (E)) (C (F)))

Solution 2:

There's a scary way of doing it using just cons:

(defn mktree 
  ([label l r] (cons label (cons l r))) 
  ([leaf] (cons leaf (cons nil nil))))
(defn getlabel [t] (first t))
(defn getchildren [t] (rest t))
(defn getleft [t] (first (getchildren t)))
(defn getright [t] (rest (getchildren t)))

Note that children isn't a list; it's a pair. If your trees aren't just binary, you could make it a list. use nil when there's no left or right child, of course.

Otherwise, see this answer.

The tree in your picture:

(mktree 'A (mktree 'B (mktree 'D) (mktree 'E)) (mktree 'C nil (mktree 'F)))

Solution 3:

Trees underly just about everything in Clojure because they lend themselves so nicely to structural sharing in persistent data structure. Maps and Vectors are actually trees with a high branching factor to give them bounded lookup and insert time. So the shortest answer I can give (though it's not really that useful) is that I really recommend Purely functional data structures by Chris Okasaki for a real answer to this question. Also Rich Hickey's video on Clojure data structures on blip.tv

(set 'A 'B 'C)