B-tree

btree.erl

%% filename clashes with erlang module btree!

-module(btree).
-export([find/2, min/1, max/1, insert/1, insert/2, print/1, print/2]).

-record(node, {val, left = nil, right = nil}).

%% find a specific value in a tree, or not_found
find(Value, Node) when Value == Node#node.val ->
    {ok, Node};
find(Value, Node) when Value > Node#node.val ->
    find(Value, Node#node.right);
find(Value, Node) when Value < Node#node.val ->
    find(Value, Node#node.left);
find(_, nil) ->
    not_found.

%% find min node in a tree
min(Node) when Node#node.left == nil ->
    Node;
min(Node) ->
    min(Node#node.left).

%% find max node in a tree
max(Node) when Node#node.right == nil ->
    Node;
max(Node) ->
    max(Node#node.right).

%% create a new tree
insert(Value) ->
    #node{val = Value}.

%% insert value into a tree
insert(Value, nil) ->
    insert(Value);
insert(Value, Tree) when Tree#node.val == nil ->
    insert(Value);
insert(Value, Tree) when Value > Tree#node.val ->
    Tree#node{right = insert(Value, Tree#node.right)};
insert(Value, Tree) when Value < Tree#node.val ->
    Tree#node{left = insert(Value, Tree#node.left)}.

%% in-order print
print(nil) ->
    nil;
print(Tree) ->
    btree:print(Tree#node.left),
    io:format("~p~n", [Tree#node.val]),
    btree:print(Tree#node.right).

%% preorder and postorder print
print(nil, _) ->
    nil;
print(Tree, Order) when Order == preorder ->
    io:format("~p~n", [Tree#node.val]),
    btree:print(Tree#node.left),
    btree:print(Tree#node.right);
print(Tree, _) ->
    btree:print(Tree#node.left),
    btree:print(Tree#node.right),
    io:format("~p~n", [Tree#node.val]).