-module(tree).        %% tree.erl
-compile(export_all).

%% @type btr() = leaf | {any(),btr(),btr()}.

empty() -> leaf.

node(V, Lt, Rt) -> {V,Lt,Rt}.

max(X,Y) when X>Y -> X; max(_X,Y) -> Y.

depth(leaf) -> 0;
depth({_,Lt,Rt}) -> 1 + max(depth(Lt), depth(Rt)).

leaves(leaf) -> 1;
leaves({_,Lt,Rt}) -> leaves(Lt) + leaves(Rt).

%%                 1
%%             2       5
%%           3   4   6   7
%%          - - - - - - - -

btr(1) ->
    L = empty(),
    node(1,
	 node(2,
	      node(3,L,L),
	      node(4,L,L)
             ),
         node(5,
	      node(6,L,L),
	      node(7,L,L)
	     )
	).

listToTree([]) ->
    empty();
listToTree(L) ->
    {L1,L2} = lists:split(length(L) div 2, L),
    node(hd(L2), listToTree(L1), listToTree(tl(L2))).

ilist(N) -> lists:seq(1,N,1).

alist(F,N) -> lists:map(fun(X) -> list_to_atom([X-1+F]) end, ilist(N)).

treeToList_in(leaf) ->
    [];
treeToList_in({V,Lt,Rt}) ->
    treeToList_in(Lt) ++ [V] ++ treeToList_in(Rt).

treeToList_pre(leaf) ->
    [];
treeToList_pre({V,Lt,Rt}) ->
    [V] ++ treeToList_pre(Lt) ++ treeToList_pre(Rt).