ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Nov 24 2019
·
0 comments

Instructions

Test suite

Solution

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
```

In order to run the tests for this track, you will need to install DUnitX. Please see the installation instructions for more information.

If Delphi is properly installed, and `*.dpr`

file types have been associated with Delphi, then double clicking the supplied `*.dpr`

file will start Delphi and load the exercise/project. `control + F9`

is the keyboard shortcut to compile the project or pressing `F9`

will compile and run the project.

Alternatively you may opt to start Delphi and load your project via. the `File`

drop down menu.

We monitor the Pascal-Delphi support room on gitter.im to help you with any questions that might arise.

Note that, when trying to submit an exercise, make sure the exercise file you're submitting is in the `exercism/delphi/<exerciseName>`

directory.

For example, if you're submitting `ubob.pas`

for the Bob exercise, the submit command would be something like `exercism submit <path_to_exercism_dir>/delphi/bob/ubob.pas`

.

Josh Cheek https://twitter.com/josh_cheek

It's possible to submit an incomplete solution so you may request help from a mentor.

```
unit uBinarySearchTreeTests;
interface
uses
DUnitX.TestFramework, uBinarySearchTree;
const
CanonicalVersion = '1.0.0.1';
type
[TestFixture]
TBinarySearchTreeTest = class(TObject)
private
FBSTree: TBinarySearchTree;
procedure CompareArrays(Array1, Array2: TArray<string>);
public
[TearDown]
procedure TearDown;
[Test]
// [Ignore('Comment the "[Ignore]" statement to run the test')]
procedure data_is_retained;
[Test]
[Ignore]
procedure smaller_number_at_left_node;
[Test]
[Ignore]
procedure same_number_at_left_node;
[Test]
[Ignore]
procedure greater_number_at_right_node;
[Test]
[Ignore]
procedure can_create_complex_tree;
[Test]
[Ignore]
procedure can_sort_single_number;
[Test]
[Ignore]
procedure can_sort_if_second_number_is_smaller_than_first;
[Test]
[Ignore]
procedure can_sort_if_second_number_is_same_as_first;
[Test]
[Ignore]
procedure can_sort_if_second_number_is_greater_than_first;
[Test]
[Ignore]
procedure can_sort_complex_tree;
end;
implementation
uses
System.SysUtils;
procedure TBinarySearchTreeTest.can_create_complex_tree;
begin
FBSTree := TBinarySearchTree.Create(['4', '2', '6', '1', '3', '5', '7']);
Assert.AreEqual('4', FBSTree.Data);
Assert.AreEqual('2', FBSTree.Left.Data);
Assert.AreEqual('1', FBSTree.Left.Left.Data);
Assert.AreEqual('3', FBSTree.Left.Right.Data);
Assert.AreEqual('6', FBSTree.Right.Data);
Assert.AreEqual('5', FBSTree.Right.Left.Data);
Assert.AreEqual('7', FBSTree.Right.Right.Data);
end;
procedure TBinarySearchTreeTest.can_sort_complex_tree;
begin
FBSTree := TBinarySearchTree.Create(['2', '1', '3', '6', '7', '5']);
CompareArrays(['1', '2', '3', '5', '6', '7'], FBSTree.SortedData);
end;
procedure TBinarySearchTreeTest.can_sort_if_second_number_is_greater_than_first;
begin
FBSTree := TBinarySearchTree.Create(['2', '3']);
CompareArrays(['2', '3'], FBSTree.SortedData);
end;
procedure TBinarySearchTreeTest.can_sort_if_second_number_is_same_as_first;
begin
FBSTree := TBinarySearchTree.Create(['2', '2']);
CompareArrays(['2', '2'], FBSTree.SortedData);
end;
procedure TBinarySearchTreeTest.can_sort_if_second_number_is_smaller_than_first;
begin
FBSTree := TBinarySearchTree.Create(['4', '2']);
CompareArrays(['2', '4'], FBSTree.SortedData);
end;
procedure TBinarySearchTreeTest.can_sort_single_number;
begin
FBSTree := TBinarySearchTree.Create(['4']);
CompareArrays(['4'], FBSTree.SortedData);
end;
procedure TBinarySearchTreeTest.CompareArrays(Array1, Array2: TArray<string>);
var
i: integer;
begin
Assert.AreEqual(Length(Array1), Length(Array2), ' - Array lengths must be equal');
for i := Low(Array1) to High(Array1) do
Assert.AreEqual(Array1[i], Array2[i], format('Expecting element %d to = %s, Actual = %s',
[i, Array1[i], Array2[i]]));
end;
procedure TBinarySearchTreeTest.data_is_retained;
begin
FBSTree := TBinarySearchTree.Create(['4']);
Assert.AreEqual('4', FBSTree.Data);
end;
procedure TBinarySearchTreeTest.greater_number_at_right_node;
begin
FBSTree := TBinarySearchTree.Create(['4', '5']);
Assert.AreEqual('4', FBSTree.Data);
Assert.AreEqual('5', FBSTree.Right.Data);
end;
procedure TBinarySearchTreeTest.same_number_at_left_node;
begin
FBSTree := TBinarySearchTree.Create(['4', '4']);
Assert.AreEqual('4', FBSTree.Data);
Assert.AreEqual('4', FBSTree.Left.Data);
end;
procedure TBinarySearchTreeTest.smaller_number_at_left_node;
begin
FBSTree := TBinarySearchTree.Create(['4', '2']);
Assert.AreEqual('4', FBSTree.Data);
Assert.AreEqual('2', FBSTree.Left.Data);
end;
procedure TBinarySearchTreeTest.TearDown;
begin
FBSTree.Free;
end;
initialization
TDUnitX.RegisterTestFixture(TBinarySearchTreeTest);
end.
```

```
unit uBinarySearchTree;
interface
type
TDatum = string;
TData = TArray<TDatum>;
TNode = class
public
Data: TDatum;
Right, Left: TNode;
private
procedure AddDatum(Datum: TDatum);
procedure GetData(var SortedData: TData);
end;
TBinarySearchTree = class(TNode)
public
function SortedData: TData;
constructor Create(Data: TData);
end;
implementation
uses
SysUtils;
{ TBinarySearchTree }
constructor TBinarySearchTree.Create(Data: TData);
var
Datum: TDatum;
begin
for Datum in Data do
Self.AddDatum(Datum);
end;
function TBinarySearchTree.SortedData: TData;
begin
Self.GetData(Result);
end;
{ TNode }
procedure TNode.AddDatum(Datum: TDatum);
procedure CreateIfNil(var Node: TNode);
begin
if not Assigned(Node) then
Node := TNode.Create;
end;
begin
if Data.IsEmpty then begin
Data := Datum;
end else if Data < Datum then begin
CreateIfNil(Right);
Right.AddDatum(Datum);
end else if Data >= Datum then begin
CreateIfNil(Left);
Left.AddDatum(Datum);
end;
end;
procedure TNode.GetData(var SortedData: TData);
procedure GetDataIfAssigned(Node: TNode; var SortedData: TData);
begin
if Assigned(Node) then
Node.GetData(SortedData);
end;
begin
GetDataIfAssigned(Left, SortedData);
SortedData := SortedData + [Data];
GetDataIfAssigned(Right, SortedData);;
end;
end.
```

A huge amount can be learned from reading other peopleâ€™s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

- What compromises have been made?
- Are there new concepts here that you could read more about to improve your understanding?

Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments