# exercism-perl5

Repository for my Perl 5 Exercism exercises
git clone git://git.samirparikh.com/exercism-perl5
Log | Files | Refs | README

```      1 # Binary Search Tree
2
3 Welcome to Binary Search Tree on Exercism's Perl 5 Track.
4 If you need help running the tests or submitting your code, check out `HELP.md`.
5
6 ## Instructions
7
8 Insert and search for numbers in a binary tree.
9
10 When we need to represent sorted data, an array does not make a good
11 data structure.
12
13 Say we have the array `[1, 3, 4, 5]`, and we add 2 to it so it becomes
14 `[1, 3, 4, 5, 2]` now we must sort the entire array again! We can
15 improve on this by realizing that we only need to make space for the new
16 item `[1, nil, 3, 4, 5]`, and then adding the item in the space we
17 added. But this still requires us to shift many elements down by one.
18
19 Binary Search Trees, however, can operate on sorted data much more
20 efficiently.
21
22 A binary search tree consists of a series of connected nodes. Each node
23 contains a piece of data (e.g. the number 3), a variable named `left`,
24 and a variable named `right`. The `left` and `right` variables point at
25 `nil`, or other nodes. Since these other nodes in turn have other nodes
26 beneath them, we say that the left and right variables are pointing at
27 subtrees. All data in the left subtree is less than or equal to the
28 current node's data, and all data in the right subtree is greater than
29 the current node's data.
30
31 For example, if we had a node containing the data 4, and we added the
32 data 2, our tree would look like this:
33
34       4
35      /
36     2
37
38 If we then added 6, it would look like this:
39
40       4
41      / \
42     2   6
43
44 If we then added 3, it would look like this
45
46        4
47      /   \
48     2     6
49      \
50       3
51
52 And if we then added 1, 5, and 7, it would look like this
53
54           4
55         /   \
56        /     \
57       2       6
58      / \     / \
59     1   3   5   7
60
61 ## Source
62
63 ### Created by
64
65 - @bentglasstube
66
67 ### Contributed to by
68
69 - @kytrinyx
70 - @m-dango
71 - @rfilipo
72
73 ### Based on
74