t.erl

-module(t).

-export([t/0]).

-define(empty_tree,
        #node{root = undefined, left = undefined, right = undefined}).

-record(node, {root, left, right}).

t() ->
    t("gfekjmlinhpoqdutsrvcbxwyaBAzEDGFC",
      "gfkmljnipqoheutsvrdcxywbBAEGFDCza",
      {"abcdefghijklmnopqrstuvwxyzABCDEFG",
       "Wec_otphsaeamDaB_iert_otolm_ejn_A"}).

t(Mid, Last, {Prev, XX}) ->
    Tree = from_last_mid(Last, Mid),
    NewTree = map_tree(Tree, generate_mapping(Prev, XX)),
    bfs(NewTree).

from_last_mid([], _) ->
    undefined;
from_last_mid(_, []) ->
    undefined;
from_last_mid(Last, Mid) ->
    {Root, LastTail} = split_root_from_last(Last),
    case split_left_right_from_mid(Root, Mid) of
        {Left, Right} ->
            #node{root = Root, left = from_last_mid(LastTail, Left),
                  right = from_last_mid(LastTail, Right)};
        _ ->
            from_last_mid(LastTail, Mid)
    end.

split_root_from_last(Last) ->
    split_root_from_last_do(lists:reverse(Last)).

split_root_from_last_do([Root | Tail]) ->
    {Root, lists:reverse(Tail)}.

split_left_right_from_mid(Root, MidList) ->
    case lists:member(Root, MidList) of
        true ->
            split_left_right_from_mid(Root, MidList, [], []);
        _ ->
            not_found
    end.

split_left_right_from_mid(_, [], Left, Right) ->
    {lists:reverse(Left), Right};
split_left_right_from_mid(Root, [Root | T], Left, _) ->
    split_left_right_from_mid(Root, [], Left, T);
split_left_right_from_mid(Root, [H | T], Left, Right) ->
    split_left_right_from_mid(Root, T, [H | Left], Right).

map_tree(undefined, _) -> undefined;
map_tree(#node{root = Root, left = Left, right = Right}, Mapping) ->
    #node{root = proplists:get_value(Root, Mapping),
          left = map_tree(Left, Mapping),
          right = map_tree(Right, Mapping)}.

generate_mapping(Old, New) ->
    generate_mapping(Old, New, []).

generate_mapping([], [], Res) ->
    Res;
generate_mapping([H1 | T1], [H2 | T2], Res) ->
    generate_mapping(T1, T2, [{H1, H2} | Res]).

bfs(?empty_tree) -> [];
bfs(Tree) -> bfs_do([Tree], []).

bfs_do([], ResList) ->
    lists:reverse(ResList);
bfs_do([#node{root = Root, left = Left, right = Right} | Tail], ResList) ->
    NewTail = [X || X <- Tail ++ [Left, Right], X =/= undefined],
    bfs_do(NewTail, [Root | ResList]).