Otherwise, everything important is done in the insert subroutine and it seems to be it is pretty much straight forward: if the value of the current node is larger than the value to be inserted, go down into the left subtree (by calling recursively insert on it); if it is larger, go down into the right subtree (also calling insert recursively); if it is equal, it is a duplicate, just ignore it; if the node is not defined, then create it, you're at the right place.

What is it that you don't understand?

I'll note that for those severely budget-constrained, the older versions of The Perl CD Bookshelf from O'Reilly are really affordable. $4 shipped plus any applicable tax in the US, for example, is a good deal if you don't need the latest version. This doesn't support the authors and publisher as much as a brand new book, but it's legal and far more ethical than using pirated copies.

Here's what the second version of the CD Bookshelf included:

• Programming Perl, third edition
• Perl for System Administration
• Perl in a Nutshell
• Perl Cookbook
• Advanced Perl Programming

There are also some good books that are actually gratis for personal use in electronic form. There's a huge GitHub project for free programming book lists at https://github.com/vhf/free-programming-books with various languages including English used for the lists. Of course there's a Perl section among many other languages and programming-language-neutral programming topics.

HI Laurent,
Thanks for the response. The part which I do not understand is , how are the nodes inserted after a second node has been created.
So say for instance the first node is with value 40. So this node now contains undefined references to the Left and Right node.
Now say the second value that is generated is 60 , This is inserted to the Right of the tree. So $tree->{right} points a new tree with value 60.

( I understand till here) But now say if third value that is generated is 80 . At this point in time $root still points to the orignal tree with value 40.
Now because $root is already defined it skips to the if else condition , and makes a call that 80 > 40 , hence it should be inserted to the right
But $tree->{Right} is already defined , and it contains the value 60, so it never executes the actual routine to create a reference to a new tree .....


So I am confused about the way they are using references to move things around.....

And what if the third value that is generated is 50 . 50 >40 hence it will be inserted at the right. But 50<60 , so it should be inserted to the left of 60 in its tree.
How is this determined in the code ?
Will appreciate any help you can provide to clear my understanding....

But now say if third value that is generated is 80 . At this point in time $root still points to the orignal tree with value 40. Now because $root is already defined it skips to the if else condition , and makes a call that 80 > 40 , hence it should be inserted to the right But $tree->{Right} is already defined , and it contains the value 60, so it never executes the actual routine to create a reference to a new tree

Yes, $tree->{Right} is already defined, so it recurses again, and inserts 80 as the right son of 60.

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]

( I understand till here) But now say if third value that is generated is 80 . At this point in time $root still points to the orignal tree with value 40. Now because $root is already defined it skips to the if else condition , and makes a call that 80 > 40 , hence it should be inserted to the right But $tree->{Right} is already defined , and it contains the value 60, so it never executes the actual routine to create a reference to a new tree .....

Follow what is happening:

- and makes a call that 80 > 40 , hence it should be inserted to the right

Yes. So it calls the insert function on the right tree. When entering this new function call, it finds a node where the value is 60. It compares the values, and since 80 is larger than 60, it sees that it should call the insert function recursively once more on the right side. When it gets to this next level, the node below 60 does not exists yet, so that insert can actually create the node 80 below (and right of) node 60.

Update ( Dec 06, 2015 at 22:25 UTC):

This graph may make it clearer:

          40
         /  \
        /    \
             60
            /  \
                \
                80
[download]

Now, if you add another node with a value of 50, it will go right of 40 and then left of 60:

          40
         /  \
        /    \
             60
            /  \
           /    \
          50    80
[download]

Update 2:

And, since you appear not to have seen my earlier warning, let me repeat that the link you're giving on the O'Reilly books is on a site (presumably in Ukraine) which most probably does not have the right to publish these contents on the Internet.

In other words, it is most probably illegal, and I would advise again you to update your original post and remove the link.

Welcome to perlmonks,
As usually stated in those case, this is not an online code writing service.

What have you tried? If you post a bit of code or at least your ideas on how you would go about it (what perl built in structure you might use) you might get help!

So before you hit google with "binary tree implementation" you might as well have a look at this if you feel in an array using mood
You might also implement your tree as a serie of hash data structures with references to each other
Update:
as explained in the link above, after the second node has been added you just recursively use the same action to add new nodes:

Is that value bigger than the first node?
then recurse right
else recurse left
and so on.
When updating the tree you add references to the new values that way they are not lost, that means that once you have found a place for the new value in your tree you update the new node's father with a reference to his child (here in left or right field)

Update 2
Just to be clear, when I say recurse I mean, call the function inside itself, using recursion that is. If you understand the concept that kind of data structure becomes much easier to handle

Hello punitpawar,

I am trying to write a program that will create a binary tree for any 10 random numbers that are generated.

From your later posts, it appears that you actually want a sorted binary tree. has various modules you can use for this. Here is one example:

#! perl
use strict;
use warnings;
use Tree::Binary::Search;
use Tree::Binary::Visitor::InOrderTraversal;

for (1 .. 20)
{
    my $btree = Tree::Binary::Search->new;
       $btree->useNumericComparison;

    for (1 .. 10)
    {
        my $num = int rand 100;
        redo if $btree->exists($num);
        $btree->insert($num => 1);
    }

    my $visitor = Tree::Binary::Visitor::InOrderTraversal->new;
       $visitor->setNodeFilter(sub { $_[0]->getNodeKey });

    $btree->accept($visitor);
    print join(' ', map { sprintf '%2d', $_ } $visitor->getResults), "
+\n";
    $btree->DESTROY;
}
[download]

Output:

13:09 >perl 1475_SoPW.pl
 0  9 14 33 37 55 60 77 89 99
15 26 28 51 59 75 78 79 94 99
18 31 33 38 44 47 70 73 77 84
 4 21 24 28 38 57 65 76 98 99
16 42 50 62 70 71 83 87 92 94
21 29 35 40 49 68 71 79 85 90
 2  5 11 16 24 46 50 55 75 99
19 26 28 39 42 51 53 59 66 98
26 35 41 45 53 54 67 81 88 95
19 28 45 51 58 64 65 67 79 82
 0 21 27 54 60 63 64 73 78 99
 0  5 13 27 31 50 61 74 77 92
11 13 14 29 52 60 71 79 80 86
 8  9 29 36 37 50 58 69 81 82
10 14 23 38 46 53 57 67 90 97
 7  8 13 14 30 32 34 41 50 76
 6 11 21 28 50 53 78 79 96 98
19 24 28 37 60 71 78 85 88 93
14 26 28 31 42 59 71 83 87 94
 0  8 13 15 19 51 52 71 78 85

13:09 >
[download]

As you can see, in-order traversal outputs the numbers in sorted (numerical ascending) order, showing that the underlying binary tree is sorted.

Hope that helps,