package BinTree;
use strict;

##########################################################
# Public interface to class "BinTree":
##########################################################

# CONSTRUCTORS
sub new($);	    # basic constructor: $t = BinTree->new();
sub copy($);	    # copy constructor:  $t2 = $t1->copy();

# DESTRUCTOR is unneeded: Perl does its own GC for the simple stuff

# INSTANCE METHODS
sub insert($);	    # insert a node into a tree:  $t->insert($node);
sub remove($);	    # remove a node from a tree:  $t->remove($node);
sub search($);	    # find a node in a tree:      $n = $t->search($value)

sub inorder($);    # inorder traversal:           $t->inorder(\&func);
sub postorder($);  # postorder traversal:         $t->postorder(sub { });
sub preorder($);   # preorder traversal:          $t->preorder(\&whatever);

##########################################################
# Private implementation to class "BinTree":
##########################################################

###########################################################
#   A tree node is represented by a structure (hash ref)  #
#   consisting of three fields:				  #
#       VALUE	Whatever the user inserted there	  #
#       LEFT	The left child			          #
#       RIGHT	The right child				  #
###########################################################

use Carp;

sub new($) {
    my ($class, $value) = @_;
    $class = ref $class if ref $class;
    my $tree  = {
	VALUE	=> $value,
	LEFT	=> undef,
	RIGHT	=> undef,
    };
    bless($tree, $class);
    return $tree;
}

sub insert($) {
    my($tree, $value) = @_;

    if (!defined $tree->{VALUE}) {
	$tree->{VALUE} = $value;
    } 
    elsif ($tree->{VALUE} > $value) {
	if ($tree->{LEFT})  { $tree->{LEFT}->insert($value)      }
	else 		    { $tree->{LEFT} = $tree->new($value) } 
    } 
    elsif ($tree->{VALUE} < $value) {
	if ($tree->{RIGHT}) { $tree->{RIGHT}->insert($value)      }
	else 		    { $tree->{RIGHT} = $tree->new($value) } 
    } 
    else {
	carp "Duplicate insertion of $value ignored";
    } 
} 

sub inorder($) {
    my($tree, $coderef) = @_;
    $tree->{LEFT}->inorder($coderef)   if $tree->{LEFT};
    $coderef->($tree->{VALUE});
    $tree->{RIGHT}->inorder($coderef)  if $tree->{RIGHT};
} 

sub preorder($) {
    my($tree, $coderef) = @_;
    $tree->{LEFT}->preorder($coderef)   if $tree->{LEFT};
    $tree->{RIGHT}->preorder($coderef)  if $tree->{RIGHT};
    $coderef->($tree->{VALUE});
} 

sub postorder($) {
    my($tree, $coderef) = @_;
    $tree->{RIGHT}->postorder($coderef) if $tree->{RIGHT};
    $tree->{LEFT}->postorder($coderef)  if $tree->{LEFT};
    $coderef->($tree->{VALUE});
} 

sub search($) {
    my($tree, $value) = @_;
    return unless $tree;
    if ($tree->{VALUE} == $value) {
	return $tree;
    } 
    my $branch = ($value < $tree->{VALUE}) ? "LEFT" : "RIGHT";
    return  $tree->{$branch}  && $tree->{$branch}->search($value);
} 

sub remove($) { confess "UNIMPLEMENTED" }
sub copy($)   { confess "UNIMPLEMENTED" }

1;