Editing Cons (section)

===Trees===
[[Binary tree]]s that only store data in their [[Leaf node|leaves]] are also easily constructed with {{lisp2|cons}}. For example, the code:

 <syntaxhighlight lang="lisp">(cons (cons 1 2) (cons 3 4))</syntaxhighlight>

results in the tree:

 ((1 . 2) . (3 . 4))

i.e.

    *
   / \
  *   *
 / \ / \
 1 2 3 4

Technically, the list (1 2 3) in the previous example is also a binary tree, one which happens to be particularly unbalanced. To see this, simply rearrange the diagram:

  *--*--*--nil
  |  |  |
  1  2  3

to the following equivalent:

    *
   / \
  1   *
     / \
    2   *
       / \
      3  nil