"Use of uninitialized value in numeric eq (==) at Tree.pl line 42.
Use of uninitialized value in numeric eq (==) at Tree.pl line 42."
##</code><code>##

use strict;
use warnings;

sub search {
	my ($tree, $element) = @_; # we pass the root node and the element to be found
	my $node;
	
	while($node = $$tree) { # $tree is a reference so we dereference it using $$.
		if($element == $node->{val}) {
			return($tree, $node); # return the subtree where the node was found.
		} else {
			if($element < $node->{val}) {
				# go left
				$tree = \$node->{left}; # note that $tree is a reference so we assign it a reference with '\'
			} else {
				$tree = \$node->{right};
			}
		}
	} # we reach here iff there is no $element to be found
	# we politely suggest user that they may add the element at the given position.
	return ($tree, undef);
}

sub insert {
	my ($tree, $element) = @_;
	my $found;
	($tree, $found) = search($tree, $element);
	
	unless($found) {
		$found = {
			left => undef,
			right => undef,
			val => $element,
		};
		$$tree = $found;
	}
	return $found;
}

sub traverse {
	my $tree = shift;
	if($$tree->{left} == undef || $$tree->{right} == undef) {
		return;
	}
	traverse(\$tree->{left});
	print $$tree->{val};
	print "\n";
	traverse(\$tree->{right});
}

my @ele = [1, 2, 3, 4, 5];

my ($tree, $stat, $link);

for my $ele (@ele) {
	($stat, $link) = insert(\$tree, $ele);
}

traverse(\$tree);