Perl - Binary tree

Binary tree is a tree data structure in which each node has at most two child nodes (left child and right child), a binary search tree (BST) is an extension of binary tree, in which all the nodes are sorted by the following rules:

• The left subtree of a node contains only nodes with keys less than the node's key
• The right subtree of a node contains only nodes with keys greater than the node's key
• The left and right subtree must each also be a binary search tree
• There must be no duplicate nodes.

The search complexity:

Let's assuming the number of there are total number of n nodes, and the height of the tree is h, so we have
n = 1 + 2 + 4 + 8 + ... + 2^(h-1) + 2^h = 2^(h+1) - 1
n + 1 = 2^(h+1), solving this, we have
h = O(logn)

The advantage of binary tree:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move subtrees around with minumum effort

Tree Traversals:
Tree traversal means visit all the nodes in the tree. Basically there are two kinds:

• depth-first
• breadth-first

There are three different types of depth-first traversals:

1. PreOrder traversal - visit the parent first and then left and right children;
2. InOrder traversal - visit the left child, then the parent and the right child;
3. PostOrder traversal - visit left child, then the right child and then the parent;

There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.

I provide a In-order traversal BST here:

#!/usr/bin/perl
use strict;
use warnings;

my $root = undef;    # The root node, emprty at the beginning
my $n = 0;           # number of nodes

# We generate 10 random inserts
while ($n++ < 10) {insert($root, int(rand(1000)))}

# Output the whole tree, in order, recurse on left child,
# then show current value, then recurse on the right child.
print "In order: "; in_order($root); print "\n";

# Binary tree search
my $number = <>;
chomp($number);
my $found = search($root, $number);
if ($found) {
    print "Found $number at $found\n";
}
exit;

# Insert given value into proper point of
# provided tree. If no tree provided, we
# will create one
sub insert {
    my ($tree, $value) = @_;
    if (!$tree) {
        $tree = {};                   # allocate new node
        $tree->{VALUE} = $value;
        $tree->{LEFT}  = undef;
        $tree->{RIGHT} = undef;
        $_[0] = $tree;               # $_[0] is reference param
        print "|$_[0] - $_[1]|\n";
        return;
    }
    if ($tree->{VALUE} > $value)    { insert($tree->{LEFT}, $value) }
    elsif ($tree->{VALUE} < $value) { insert($tree->{RIGHT}, $value) }
    else                            { warn "duplicate insert of $value\n" }
}

# recurse on left child, then show current value,
# then recurse on right child.
sub in_order {
    my ($tree) = @_;
    return unless $tree;
    in_order($tree->{LEFT});
    print $tree->{VALUE}, " ";
    in_order($tree->{RIGHT});
}

# find out whether the provided value is in the tree.
# we only looking in the correct branch, cut down some search time
sub search {
    my ($tree, $value) = @_;
    return unless $tree;
    #print "tree->{value} = $tree->{VALUE}, value = $value\n";
    if ($tree->{VALUE} == $value) {
        return $tree;
    }
    search($tree->{ ($value < $tree->{VALUE}) ? "LEFT" : "RIGHT"}, $value)
}

Reference: http://docstore.mik.ua/orelly/perl/cookbook/ch11_16.htm