🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉 # Greycoat21's solution

## to Binary Search Tree in the Delphi Pascal Track

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

## Testing

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

### Loading Exercises into Delphi

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.

### When Questions Come Up

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

### Submitting Exercises

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

## Source

Josh Cheek https://twitter.com/josh_cheek

## Submitting Incomplete Solutions

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

### uBinarySearchTreeTests.pas

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

## Community comments

Find this solution interesting? Ask the author a question to learn more.

### What can you learn from this solution?

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?