buildtree.erl

-module(buildtree).
-compile([export_all]).

tree_from_preorder(Preorder) ->
    {T, []} = tree_from_preorder(Preorder, none),
    T.

tree_from_preorder([Root | Rest], Parent = {Root}) ->
    %% Not sure why you would want to eliminate duplicates, but ok.
    tree_from_preorder(Rest, Parent);
tree_from_preorder([Root | Rest], Parent)
  when Parent =:= none; Root < element(1, Parent) ->
    {L, RestL} = tree_from_preorder(Rest, {Root}),
    {R, RestR} = tree_from_preorder(RestL, Parent),
    {{Root, L, R}, RestR};
tree_from_preorder(Preorder, _Parent) ->
    {none, Preorder}.

preorder(T) ->
    lists:reverse(preorder(T, [])).

preorder(none, Acc) ->
    Acc;
preorder({Root, L, R}, Acc) ->
    preorder(R, preorder(L, [Root | Acc])).