# Tree operations

One of the datatypes Arc supports is binary trees, built out of cons cells. A standard technique in Lisp is to build a binary tree with data at the leaves and cons cells as the interior nodes. For example, the above balanced tree is expressed as `((1 . 2) . (3 . 4))`, which is normally displayed as `((1 . 2) 3 . 4)`. The tree does not need to be balanced, for instance, the above tree is `(((1 . 2) . 3) . 4)`.

Arc provides a few operations on binary trees. However, Arc provides no explicit support for generating binary trees. The primitive `cons` can be used to join two nodes or subtrees into a tree. The primitives `car` and `cdr` will return the left and right subtrees (or nodes) respectively.

```arc> (= mytree (cons (cons 1 2) (cons 3 4)))
((1 . 2) 3 . 4)
arc> (car mytree)
(1 . 2)
arc> (cdr mytree)
(3 . 4) treewise join base tree Recursively traverses a binary tree. The `base` function (of one argument) is applied to each leaf, and then the `join` function (of two arguments) is recursively called on each pair of branches to join together the results into the final result. `treewise` was called `trav` prior to arc2. ```>(treewise + sqrt '(1 . (4 . 9))) 6 ``` ```>(treewise + string '(1 . (4 . 9))) "149" ``` tree-subst old new tree Generates a new, modified tree. Node(s) with the value `old` are replaced with `new` in the tree. ```>(tree-subst 1 9 '((1 . 2) . (3 . 4))) ((9 . 2) 3 . 4) ``` ontree f tree Function `f` is recursively applied to the tree in prefix order, that is first the node, then the left subtree, then the right subtree. Subtrees as well as nodes are passed to `f`. ```>(ontree prn '((1 . 2) . (3 . 4))) ((1 . 2) 3 . 4) (1 . 2) 1 2 (3 . 4) 3 4 nil ```