## Wednesday, July 10, 2013

### 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)

• 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
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;
\$_ = \$tree;               # \$_ is reference param
print "|\$_ - \$_|\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