package BinarySearchTree;
use strict;
use warnings;
use Exporter qw<import>;
our @EXPORT_OK = qw<tree treeSort>;

#
# implementation of binary search tree
# as demonstrated in "Perl Cookbook" by Tom Christiansen and Nathan Torkington
# https://www.oreilly.com/library/view/perl-cookbook/1565922433/
#

sub create_new_node {
    my $value      = shift;
    # create anonymous array to represent the new node
    my $tree       = {};
    $tree->{data}  = $value;
    $tree->{left}  = undef;
    $tree->{right} = undef;
    return $tree;
}

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

    # if node we want to insert (at any location in the tree) does not exist,
    # create it and return a reference to the anonymous array containing it
    # by updating the value that was passed to the subroutine ($tree)
    unless ( $tree ) {
        $_[0] = create_new_node ( $value );
        return; # need to return since we just created a new node
    }

    # recursively find where to place new node in the tree
    if ( $tree->{data} < $value ) { insert ( $tree->{right}, $value ) }
    else                          { insert ( $tree->{left},  $value ) }
}

sub tree {
  my ($data) = @_;
  my $tree;
  insert ( $tree, $_ ) foreach ( @{ $data } );
  return $tree;
}

# recurse on left subtree, obtain root, recurse on right tree
# until we get to empty node
sub in_order {
    my($tree) = @_;
    return () unless $tree;
    return (
        in_order($tree->{left}),
                 $tree->{data},
        in_order($tree->{right})
    );
}

# You are expected to create a tree and then do an in-order walk.
# Using the sort() function is cheating!
sub treeSort {
  my ($data) = @_;
  return [in_order( tree ( $data ) )];
}

1;