Trees are not built into the λ-interpreter (they could be) but they can be implemented using lists:

infix = lambda T.
    { : Tree e -> List e,  O(|T|)-time }
  let rec inf = lambda inT. lambda op.
    if isEmptyTree inT then op
    else
      inf (left inT) (elt inT::inf (right inT) op)
  in inf T nil

To perform infix traversal of a tree, producing a list of values:

infix = lambda T.
    { : Tree e -> List e,  O(|T|)-time }
  let rec inf = lambda inT. lambda op.
    if isEmptyTree inT then op
    else
      inf (left inT) (elt inT::inf (right inT) op)
  in inf T nil

Note that function inf above, which does all the work of traversal, has an accumulating parameter, op.

A tree can also be traversed in breadth-first order. A queue, Q, of trees is used, subtrees being taken off the front of the queue and their children, if any, being added to the other end.

BFT = lambda T.  { : Tree e -> List e }
  let rec
    Q = T :: (traverse Q 1),

    traverse = lambda Q. lambda n.
    { n is remaining length of Q }
      if n = 0 then nil else
      let rec T1 = hd Q,
              Lf = left  T1,
              Rt = right T1,
            rest = traverse tl Q
      in if isEmptyTree Lf then
           if isEmptyTree Rt then rest (n-1)
           else Rt :: rest n
         else
           Lf :: if isEmptyTree Rt then rest n
                 else Rt :: rest (n+1)

  in if isEmptyTree T then nil
     else map elt Q

Note that the queue data-structure, Q, and the function, traverse, that builds Q are mutually recursive, making this a circular program (Bird 1984; Allison 1989, 1993).

A binary search tree can be built from a given list of values:

BST = lambda L.
{ binary search tree of L; both may be infinite }
  if null L then emptyTree
  else let hdL = hd L, tlL = tl L
       in fork hdL
               (BST (filter (gt hdL) tlL))
               (BST (filter (lt hdL) tlL))

An element can be added to an existing binary search tree:

BSTadd = lambda T. lambda e.
     { : Tree e -> e -> Tree e }
  if isEmptyTree T then leaf e
  else
  let eT = elt T in
  if e = eT then T
  else if e < eT then
    fork eT (BSTadd (left T) e) (right T)
  else { e > eT }
    fork eT (left T) (BSTadd (right T) e)

and another way to build a binary search tree from a list of values, L, is

foldl BSTadd emptyTree L

 

let { scroll down! } pair = lambda x. lambda y. x :: y :: nil, {std fns} fst = lambda xy. hd xy, snd = lambda xy. hd tl xy, plus = lambda x. lambda y. x+y, {ops as fns} minus = lambda x. lambda y. x-y, times = lambda x. lambda y. x*y, over = lambda x. lambda y. x/y, lt = lambda x. lambda y. x < y, le = lambda x. lambda y. x <= y, gt = lambda x. lambda y. x > y, ge = lambda x. lambda y. x >= y, eq = lambda x. lambda y. x = y, ne = lambda x. lambda y. x <> y, even = lambda n. (n/2)*2=n, odd = lambda n. not(even n), compose = lambda p. lambda q. lambda x. p(q x) { i.e. p o q } , cons = lambda H. lambda T. H::T {constructor fn} , fork = lambda e. lambda L. lambda R. { tree ops } e::L::R::nil, leaf = lambda e. e::nil::nil::nil, emptyTree = nil, isEmptyTree = lambda T. null T, elt = lambda T. hd T, left = lambda T. hd tl T, right = lambda T. hd tl tl T in let rec map = lambda f. lambda L. { [f L1, f L2, ..., f Ln] } if null L then nil else (f hd L)::(map f tl L) , filter = lambda p. lambda L. { those elements of L that satisfy p } if null L then nil else let hdL = hd L in if p hdL then hdL::(filter p tl L) else filter p tl L , infix = lambda T. { : Tree e -> List e, O(|T|)-time } let rec inf = lambda inT. lambda op. if isEmptyTree inT then op else inf (left inT) (elt inT::inf (right inT) op) in inf T nil , BFT = lambda T. { : Tree e -> List e } let rec Q = T :: (traverse Q 1), traverse = lambda Q. lambda n. { n is remaining length of Q } if n = 0 then nil else let rec T1 = hd Q, Lf = left T1, Rt = right T1, rest = traverse tl Q in if isEmptyTree Lf then if isEmptyTree Rt then rest (n-1) else Rt :: rest n else Lf :: if isEmptyTree Rt then rest n else Rt :: rest (n+1) in if isEmptyTree T then nil else map elt Q , BST = lambda L. { binary search tree of L; both may be infinite } if null L then emptyTree else let hdL = hd L, tlL = tl L in fork hdL (BST (filter (gt hdL) tlL)) (BST (filter (lt hdL) tlL)) , BSTadd = lambda T. lambda e. { : Tree e -> e -> Tree e } if isEmptyTree T then leaf e else let eT = elt T in if e = eT then T else if e < eT then fork eT (BSTadd (left T) e) (right T) else { e > eT } fork eT (left T) (BSTadd (right T) e) in BFT (BST (2::1::2::4::1::3::4::3::nil))

output area

Reference:

L. Allison, Circular programs and self referential structures. Software Practice and Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, Feb 1989.

L. Allison, Applications of Recursively Defined Data Structures, Australian Computer Journal, 25(1), pp.14-20, 1993.