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

# dgeiger's solution

## to Binary Search Tree in the Delphi Pascal Track

Published at Sep 12 2020 · 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.

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

## 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
TBinarySearchTree = class
private
FItem: String;
FLeft: TBinarySearchTree;
FRight: TBinarySearchTree;

public

constructor Create(Items: array of String);

destructor Destroy; override;

function Left: TBinarySearchTree;
function Right: TBinarySearchTree;
function SortedData: TArray<String>;

end;

implementation

{ TBinarySearchTree }

begin
// Before we can add a node to the tree, we need to see if i goes to the
// left or right of the current node. Items greater than the current value
// go on the right, and the others go on the left.
if Item <= FItem then
// The new item is less than or equal to the current item. Do we already
// have a subtree on the left?
if FLeft = nil then
// No, we need to create the subtree
FLeft := TBinarySearchTree.Create(Item)
else
// Yes, we tell the left subtree to add the item to it's tree
else
// The new item is greater than the current item. Do we already have
// a subtree on the right?
if FRight = nil then
// No, we need to create the subtree
FRight := TBinarySearchTree.Create(Item)
else
// Yes, we tell the right subtree to add the item to it's tree
end;

constructor TBinarySearchTree.Create(Items: array of String);
var
Index: Integer;
Item: String;
begin
// Save the value of the first item in the root of the tree
FItem := Items[0];

// Initialize the left subtreeto nil, so we know it doesn't exit
FLeft := nil;

// Initialize the right subtree to nil, so we know it doesn't exit
FRight := nil;

// For all of the other items, we need to add the to the tree
for Index := 1 to Length(Items) - 1 do
end;

destructor TBinarySearchTree.Destroy;
begin
// If there is a left subtree, destroy it and set left to nil
if FLeft <> nil then
begin
FLeft.Destroy;
FLeft := nil
end;

// If there is a right subtree, destroy it and set left to nil
if FRight <> nil then
begin
FRight.Destroy;
FRight := nil
end;

inherited;
end;

function TBinarySearchTree.Left: TBinarySearchTree;
begin
// Return the left subtree
Result := FLeft;
end;

function TBinarySearchTree.Right: TBinarySearchTree;
begin
// Return the right subtree
Result := FRight;
end;

function TBinarySearchTree.SortedData: TArray<String>;
begin
// If there is a left subtree, add recursively it's data to the result array
if FLeft <> nil then
Result := Result + FLeft.SortedData;

// The item in the root goes between the left subtree and the right subtree
Result := Result + [FItem];

// If there is a right subtree, add recursively it's data to the result array
if FRight <> nil then
Result := Result + FRight.SortedData;
end;

end.``````