# empty tree = []
# tree with A as its root, L as left child, R as right child
# = [L, A, R]

#                     6
#                    / \
#                   /   \
#                  /     \
#                 /       \
#                3         8
#               . \       . .
#                  \
#                   5
#                  . .

# [[[], 3, [[], 5, []]], 6, [[], 8, []]]

left [L, a, R] == L
data [L, a, R] == a
right [L, a, R] == R

# left [[[], 3, [[], 5, []]], 6, [[], 8, []]] 
#     = [[], 3, [[], 5, []]]

# left(left [[[], 3, [[], 5, []]], 6, [[], 8, []]])
# = left([[], 3, [[], 5, []]])
# = []

# right(left [[[], 3, [[], 5, []]], 6, [[], 8, []]])
# = right([[], 3, [[], 5, []]])
# = [[], 5, []]

insert N []        == [[], N, []]
insert N [L, a, R] == [insert N L, a, R] <| N < a |> [L, a, insert N R]

# insert 7 (insert 2 (insert 5 []))
# = insert 7 (insert 2 [[], 5, []])
# = insert 7 [insert 2 [], 5, []]
# = [insert 2 [], 5, insert 7 []]
# = [[[], 2, []], 5, insert 7 []]
# = [[[], 2, []], 5, [[], 7, []]]

ispresent N [] == false
ispresent N [L, a, R] == ispresent N L <| N < a |> true <| N = a |> ispresent N R

flatten T == flat T []

flat [] sofar == sofar
flat [L, A, R] sofar == flat L (A: flat R sofar)

flatten [[[], 2, []], 5, [[[], 6, []], 7, []]]
[2, 5, 6, 7]

# flatten [[[], 2, []], 5, [[[], 6, []], 7, []]]
# = flat [[[], 2, []], 5, [[[], 6, []], 7, []]]  []
# = flat [[], 2, []] (5 : flat [[[], 6, []], 7, []]  [])
# = flat [[], 2, []] (5 : flat [[], 6, []] (7: flat [] [] )
# = flat [[], 2, []] (5 : flat [[], 6, []] (7: []) )
# = flat [[], 2, []] (5 : flat [[], 6, []] [7] )
# = flat [[], 2, []] (5 : flat [] (6: flat [] [7]))
# = flat [[], 2, []] (5 : flat [] (6: [7]))
# = flat [[], 2, []] (5 : flat [] [6, 7])
# = flat [[], 2, []] (5 : [6, 7])
# = flat [[], 2, []] [5, 6, 7]
# = flat [] (2 : flat [] [5, 6, 7])
# = flat [] (2 : [5, 6, 7]
# = flat [] [2, 5, 6, 7]
# = [2, 5, 6, 7]

build L = bld L []

bld [] T == T
bld (a:b) T == bld b (insert a T)

# build [3, 7, 5, 1] =
# = bld [3, 7, 5, 1] [] =
# = bld [7, 5, 1] (insert 3 []) =
# = bld [5, 1] = (insert 7 (insert 3 [])) =
# = bld [1] = (insert 5 (insert 7 (insert 3 []))) =
# = insert 1 (insert 5 (insert 7 (insert 3 [])))

sort L == flatten (build L)

append [] L == L
append (a:b) L == a : append b L

append [3,5,8,9] [1,4,6]
[3, 5, 8, 9, 1, 4, 6]

flatten [] == []
flatten [L,a,R] =  append  (flatten L)  (a : (flatten R))