binary-search-tree: Implement canonical-data.json

[kytrinyx]

We want to have a standard set of test inputs and outputs for each exercise to
make it easier to port them to new languages, as well as to help keep the
exercises in sync.

The Binary Search Tree exercise can be found in the ./exercises/binary-search-tree/ directory.

The step-by-step instructions for how to compile a canonical-data.json file is
described in this section of the contributing guide.

See http://exercism.io/contribute/canonical-data/binary-search-tree for the up-to-date list of
language tracks that have an implementation of the Binary Search Tree exercise.

The tracking issue has more context.

[devkabiir]

@kytrinyx I've made a few simple tests in my PR #54 of dart track.

To summarize, tests should verify the implementation of binary search tree has following
For simplicity, data is restricted to integers only.

• insert data function that returns true if success, false if :
  -Data already exists in the tree
  -Data is null
• search data function that returns true if data exists, return false if :
  -Tree is empty
  -Tree is null or equivalent of the specific track
  -Data doesn't exist in the tree
• Ascending order function that returns inorder traversal of tree,
  -empty array[]or list[] or equivalent if tree exists but is empty.
• The actual data (array/list/etc) should be private to the class or equivalent of the specific track
  -to ensure that the data cannot be changed directly accidentally, since binary search tree is a data structure and only the data structure itself should be able to manipulate the data.

I didn't need to implement all of them as dart can be (optionally) type strict. Similarly most of the type strict languages win't need to implement all. This can be a good starting point.

[kytrinyx]

This can be a good starting point.

Indeed! Thanks so much for adding this context, it's very helpful. 💙

[Stargator]

@kytrinyx should we delay implementing this exercise until a canonical-data.json is defined?

I know in the dart track's README, it states:

• All Exercism exercises must be defined in problem-specifications before they are implemented for a specific track. Please submit a PR there if your exercise is new to Exercism.

• Please make sure the new exercise conforms to specifications in the exercism/problem-specifications repo.

Since the specification is missing a canonical-data.json, does that mean it's incomplete and thus not ready for implementation?

[devkabiir]

@kytrinyx if the summary I provide is good enough I can make a PR with suggested changes.

[kytrinyx]

Since the specification is missing a canonical-data.json, does that mean it's incomplete and thus not ready for implementation?

No, canonical-data.json is optional.

We've also started allowing track-specific exercises (though in this case there's no reason to make it track-specific). I probably need to update that documentation.

[kytrinyx]

if the summary I provide is good enough I can make a PR with suggested changes.

@kabiir that would be great!

[Insti]

Have a read through: #761 before deciding if you want to spend time implementing canonical-data.json for binary-search.
Edit: This is an issue about binary-search-tree not binary-search

[NobbZ]

@Insti this thread is about the binary-search-tree exercise. An exercise related to a data structure, where the tests I've encountered so far, do expect to expose some functions which usually are only used internally when implenting such a data structure.

While the binary-search exercise you mention is an algorithmic exercise, which was originally aimed to teach the binary-search algorithm over sorted input. It can decide if an element is in the data structure O(log n) runtime on any data structure with O(1) random read. This exercise can be solved without any failing tests by simply doing a linear search through the same datastructure. Thats why we decided to remove/rework this.

So, there is no danger when collecting the canonical data for this exercise, it will not be removed or reworked thus fast ;)

[Insti]

Thanks @NobbZ, my mistake.