construct a binary tree given the inorder and preorder listing

-module(tree).

-export([empty/0, insert/3, lookup/2]).

-export([construct/2, construct_test/0]).


empty() -> {node, 'nil'}.

insert(Key, Val, {node, 'nil'}) ->
    {node, {Key, Val, {node, 'nil'}, {node, 'nil'}}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key ->
    {node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key ->
    {node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger)}};
insert(Key, Val, {node, {Key, _, Smaller, Larger}}) ->
    {node, {Key, Val, Smaller, Larger}}.

lookup(_, {node, 'nil'}) ->
    undefined;
lookup(Key, {node, {Key, Val, _, _}}) ->
    {ok, Val};
lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey ->
    lookup(Key, Smaller);
lookup(Key, {node, {_, _, _, Larger}}) ->
    lookup(Key, Larger).

construct(InOrder, PreOrder) ->
    construct(InOrder, PreOrder, empty()).

construct([], [], Tree) ->
    Tree;
construct(InOrder, PreOrder, Tree) ->
    [Root | RestPO] = PreOrder,
    %% Find Left and Right values of the root
    case find_sides(Root, InOrder) of
        {[], []} ->
            insert(Root, Root, Tree);
        {Left, Right} ->
            {LPO, RPO} = lists:split(length(Left), RestPO),
            LeftNode = construct(Left, LPO, Tree),
            RightNode = construct(Right, RPO, Tree),
            {node, {Root, Root, LeftNode, RightNode}}
    end.


find_sides(Root, InOrder) ->
    case lists:splitwith(fun(Elem) ->
                                 Elem =/= Root
                         end, InOrder) of
        {Left, []} ->
            {Left, []};
        {Left, [Root | Right]} ->
            {Left, Right}
    end.

construct_test() ->
    construct(["D", "B", "E", "A", "F", "C"],
              ["A", "B", "D", "E", "C", "F"]).