Clojure code is composed of literal representations of its own data structures and atomic values; this characteristic is formally called homoiconicity, or more casually, code-as-data. 1 It means that we can use clojure code to represent tree data structure! No more `class Tree` and `class TreeNode`.

### Binary Tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a triple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set. Some authors allow the binary tree to be the empty set as well. 2

Example:

``````;;
;;     A
;;    / \
;;   B   C
;;  / \  |
;; D   E F
;;
``````

We can easily use clojure list to represent it:

### Traverse

In clojure, we use `tree-seq` to get nodes a tree in DFS.

``````clojure.core/tree-seq
([branch? children root])
Returns a lazy sequence of the nodes in a tree, via a depth-first walk.
branch? must be a fn of one arg that returns true if passed a node
that can have children (but may not).  children must be a fn of one
arg that returns a sequence of the children. Will only be called on
nodes for which branch? returns true. Root is the root node of the
tree.
``````

Imaging Each node is a `'(root left right)`. It’s easy to reduce that:

• If `(next node)` return `nil`, that means this node has no nore branches, elase means that this node has sibling.
• If `(rest node)` return `'()`, that means this node is root; else means that this node is not root.

Traverse it: