creating a basic functional programmed bst implementation

binary_tree.erl

% Module: binary_tree
%   Exposes new binary tree syntax.
% 
%   Author: monkegjinni <[email protected]>
% 
%   Notices:
%     !These is a very naive tree implementation. In Production do not use this.
%     For more efficient and product ready tree implementation; you should check
%     otp_src_R<version>B<revision>/lib/stdlib/src/gb_trees.erl .
% 
%   Credit: goes to http://learnyousomeerlang.com/recursion#more-than-lists (:

-module( binary_tree ).

-compile([ export_all ]).


% Public: create()
%   Creates an initial binary tree node with an empty Node, Right, and Left.
%
%   Returns: an initial empty binary tree node as { Left, Key, Value, Right }
%
%   Example:
%     Tree = binary_tree:create()
%     # => Tree = { nil, nil, nil, nil }

create() ->
	{ nil, nil, nil, nil }.

% Public: insert( Tree, Key, Value )
%   Inserts given Value to the binary tree, Tree.
% 
%   Parameters:
%     Tree:  a binary tree variable that is initialized via create() 
%     and then maybe modified with insert.
%     Key:  a key to place new node its proper place in Tree.
%     Value: a value to be inserted in the new node along with the Key.
% 
%   Returns:
%     Updated tree after insertion being successful.
% 
%   Example:
%     % we had a Tree variable initialized via create(), inserted 5 and then 3.
%     % { { nil, "Acar", "[email protected]", nil }, "Ahmet", "[email protected]", nil }
% 
%     NewTree = binary_tree:insert( Tree, "Veli", "[email protected]" ).
% 
%     % =>  NewTree = { 
%     %       { nil, "Acar", "[email protected]", nil }, 
%     %       "Ahmet", "[email protected]", 
%     %       { nil, "Veli", "[email protected]" } 
%     %     }
% 
%   Notices:
%     * Tree variable must be initialized with binary_tree:create() first. 
%     You will get your Tree variable here.
%     * Insertion is seamless. If it sees corresponding node nil, 
%     then value will be inserted; no matter it is 
%     master node or not ( first node after create() ).
%     * After every insertion a new tree is created. 
%     Any comment for improvement, appreciated (:

insert( { nil, nil, nil, nil }, Key, Value ) ->
	{ nil, Key, Value, nil  };

insert( nil, Key, Value ) ->
	{ nil, Key, Value, nil };

insert( { Left, NodeKey, NodeValue, Right }, Key, Value ) when  NodeKey =/= nil, Key < NodeKey  ->
	{ insert( Left, Key, Value ), NodeKey, NodeValue, Right };

insert( { Left, NodeKey, NodeValue, Right }, Key, Value ) when NodeKey =/= nil, Key > NodeKey ->
	{ Left, NodeKey, NodeValue, insert( Right, Key, Value ) };

insert( { Left, NodeKey, NodeValue, Right }, Key, _ ) when NodeKey =/= nil, Key =:= NodeKey ->
	{ Left, NodeKey, NodeValue, Right }.


% Public: lookup( Tree, Key )
%   Searches binary tree Tree. if Key exists at any one of its nodes gives its result.
% 
%   Parameters:
%     Tree:   a binary tree form of { Left, Key, Value, Right } to be searched.
%     Key:    a value to be searched.
% 
%   Returns:  Value corresponding Key given.
% 
%   Examples:
% 
%     Tree = { 
%       {nil, "acar", "[email protected]", nil}, 
%       "Ahmet", "[email protected]", 
%       {
%         {nil, "Gaffur", "[email protected]", nil}, 
%         "Veysel", "Veysel.com", 
%         nil
%       }
%     }
% 
%     Value = binary_tree:lookup( Tree, "Gaffur" ).
%     # => "[email protected]"
% 
%     NonExistingValue = binary_tree:lookup( Tree, "Nadide" ).
%     # => nil

lookup( { _, nil, _, _ }, _ ) ->
  nil;

lookup( nil, _ ) ->
  nil;

lookup( { Left, NodeKey, _, _ }, Key ) when Key < NodeKey ->
  lookup( Left, Key );

lookup( { _, NodeKey, _, Right }, Key ) when Key > NodeKey ->
  lookup( Right, Key );

lookup( { _, NodeKey, Value, _ }, Key ) when Key =:= NodeKey ->
  Value.