commit 2f5a8088073198abd9c2ee9f76e3d80dc7932122
parent cd1c08ebfcdcfd466c25d175f7c153f5e5e3c92f
Author: Samir Parikh <noreply@samirparikh.com>
Date: Wed, 5 Jan 2022 02:14:41 +0000
get initial tests for insertion of nodes to pass
Diffstat:
4 files changed, 393 insertions(+), 0 deletions(-)
diff --git a/binary-search-tree/BinarySearchTree.pm b/binary-search-tree/BinarySearchTree.pm
@@ -0,0 +1,56 @@
+package BinarySearchTree;
+use strict;
+use warnings;
+use Exporter qw<import>;
+our @EXPORT_OK = qw<tree treeSort>;
+
+#
+# implementation of binary search tree
+# as demonstrated in "Perl Cookbook" by Tom Christiansen and Nathan Torkington
+# https://www.oreilly.com/library/view/perl-cookbook/1565922433/
+#
+
+use v5.22;
+use Data::Dumper;
+
+sub create_new_node {
+ my $value = shift;
+ # create anonymous array to represent the new node
+ my $tree = {};
+ $tree->{data} = $value;
+ $tree->{left} = undef;
+ $tree->{right} = undef;
+ return $tree;
+}
+
+sub insert {
+ my ( $tree, $value ) = @_;
+
+ # if node we want to insert (at any location in the tree) does not exist,
+ # create it and return a reference to the anonymous array containing it
+ # by updating the value that was passed to the subroutine ($tree)
+ unless ( $tree ) {
+ $_[0] = create_new_node ( $value );
+ return; # need to return since we just created a new node
+ }
+
+ # recursively find where to place new node in the tree
+ if ( $tree->{data} < $value ) { insert ( $tree->{right}, $value ) }
+ else { insert ( $tree->{left}, $value ) }
+}
+
+sub tree {
+ my ($data) = @_;
+ my $root;
+ insert ( $root, $_ ) foreach (@{$data});
+ return $root;
+}
+
+# You are expected to create a tree and then do an in-order walk.
+# Using the sort() function is cheating!
+sub treeSort {
+ my ($data) = @_;
+ return undef;
+}
+
+1;
diff --git a/binary-search-tree/HELP.md b/binary-search-tree/HELP.md
@@ -0,0 +1,35 @@
+# Help
+
+## Running the tests
+
+There is a Perl 5 script with the extension `.t`, which will be used to test
+your solution. You can run through the tests by using the command:
+
+```bash
+`prove .`
+```
+
+## Submitting your solution
+
+You can submit your solution using the `exercism submit BinarySearchTree.pm` command.
+This command will upload your solution to the Exercism website and print the solution page's URL.
+
+It's possible to submit an incomplete solution which allows you to:
+
+- See how others have completed the exercise
+- Request help from a mentor
+
+## Need to get help?
+
+If you'd like help solving the exercise, check the following pages:
+
+- The [Perl 5 track's documentation](https://exercism.org/docs/tracks/perl5)
+- [Exercism's support channel on gitter](https://gitter.im/exercism/support)
+- The [Frequently Asked Questions](https://exercism.org/docs/using/faqs)
+
+Should those resources not suffice, you could submit your (incomplete) solution to request mentoring.
+
+To get help if you're having trouble, you can use one of the following resources:
+
+- [/r/perl5](https://www.reddit.com/r/perl5) is the perl5 subreddit.
+- [StackOverflow](http://stackoverflow.com/questions/tagged/perl5) can be used to search for your problem and see if it has been answered already. You can also ask and answer questions.
+\ No newline at end of file
diff --git a/binary-search-tree/README.md b/binary-search-tree/README.md
@@ -0,0 +1,75 @@
+# Binary Search Tree
+
+Welcome to Binary Search Tree on Exercism's Perl 5 Track.
+If you need help running the tests or submitting your code, check out `HELP.md`.
+
+## Instructions
+
+Insert and search for numbers in a binary tree.
+
+When we need to represent sorted data, an array does not make a good
+data structure.
+
+Say we have the array `[1, 3, 4, 5]`, and we add 2 to it so it becomes
+`[1, 3, 4, 5, 2]` now we must sort the entire array again! We can
+improve on this by realizing that we only need to make space for the new
+item `[1, nil, 3, 4, 5]`, and then adding the item in the space we
+added. But this still requires us to shift many elements down by one.
+
+Binary Search Trees, however, can operate on sorted data much more
+efficiently.
+
+A binary search tree consists of a series of connected nodes. Each node
+contains a piece of data (e.g. the number 3), a variable named `left`,
+and a variable named `right`. The `left` and `right` variables point at
+`nil`, or other nodes. Since these other nodes in turn have other nodes
+beneath them, we say that the left and right variables are pointing at
+subtrees. All data in the left subtree is less than or equal to the
+current node's data, and all data in the right subtree is greater than
+the current node's data.
+
+For example, if we had a node containing the data 4, and we added the
+data 2, our tree would look like this:
+
+ 4
+ /
+ 2
+
+If we then added 6, it would look like this:
+
+ 4
+ / \
+ 2 6
+
+If we then added 3, it would look like this
+
+ 4
+ / \
+ 2 6
+ \
+ 3
+
+And if we then added 1, 5, and 7, it would look like this
+
+ 4
+ / \
+ / \
+ 2 6
+ / \ / \
+ 1 3 5 7
+
+## Source
+
+### Created by
+
+- @bentglasstube
+
+### Contributed to by
+
+- @kytrinyx
+- @m-dango
+- @rfilipo
+
+### Based on
+
+Josh Cheek - https://twitter.com/josh_cheek
+\ No newline at end of file
diff --git a/binary-search-tree/binary-search-tree.t b/binary-search-tree/binary-search-tree.t
@@ -0,0 +1,225 @@
+#!/usr/bin/env perl
+use Test2::V0;
+use JSON::PP;
+use constant JSON => JSON::PP->new;
+
+use FindBin qw<$Bin>;
+use lib $Bin, "$Bin/local/lib/perl5";
+
+use BinarySearchTree qw<tree treeSort>;
+
+my @test_cases = do { local $/; @{ JSON->decode(<DATA>) }; };
+
+imported_ok qw<tree treeSort> or bail_out;
+
+subtest data => sub {
+ for my $case ( grep { $_->{property} eq 'data' } @test_cases ) {
+ is( tree( $case->{input}{treeData} ),
+ $case->{expected}, $case->{description}, );
+ }
+};
+
+subtest sorting => sub {
+ for my $case ( grep { $_->{property} eq 'sortedData' } @test_cases )
+ {
+ is( treeSort( $case->{input}{treeData} ),
+ $case->{expected}, $case->{description}, );
+ }
+};
+
+done_testing;
+
+__DATA__
+[
+ {
+ "description": "data is retained",
+ "expected": {
+ "data": "4",
+ "left": null,
+ "right": null
+ },
+ "input": {
+ "treeData": [
+ "4"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "insert data at proper node: smaller number at left node",
+ "expected": {
+ "data": "4",
+ "left": {
+ "data": "2",
+ "left": null,
+ "right": null
+ },
+ "right": null
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "2"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "insert data at proper node: same number at left node",
+ "expected": {
+ "data": "4",
+ "left": {
+ "data": "4",
+ "left": null,
+ "right": null
+ },
+ "right": null
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "4"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "insert data at proper node: greater number at right node",
+ "expected": {
+ "data": "4",
+ "left": null,
+ "right": {
+ "data": "5",
+ "left": null,
+ "right": null
+ }
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "5"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "can create complex tree",
+ "expected": {
+ "data": "4",
+ "left": {
+ "data": "2",
+ "left": {
+ "data": "1",
+ "left": null,
+ "right": null
+ },
+ "right": {
+ "data": "3",
+ "left": null,
+ "right": null
+ }
+ },
+ "right": {
+ "data": "6",
+ "left": {
+ "data": "5",
+ "left": null,
+ "right": null
+ },
+ "right": {
+ "data": "7",
+ "left": null,
+ "right": null
+ }
+ }
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "2",
+ "6",
+ "1",
+ "3",
+ "5",
+ "7"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "can sort data: can sort single number",
+ "expected": [
+ "2"
+ ],
+ "input": {
+ "treeData": [
+ "2"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort if second number is smaller than first",
+ "expected": [
+ "1",
+ "2"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "1"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort if second number is same as first",
+ "expected": [
+ "2",
+ "2"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "2"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort if second number is greater than first",
+ "expected": [
+ "2",
+ "3"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "3"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort complex tree",
+ "expected": [
+ "1",
+ "2",
+ "3",
+ "5",
+ "6",
+ "7"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "1",
+ "3",
+ "6",
+ "7",
+ "5"
+ ]
+ },
+ "property": "sortedData"
+ }
+]
