🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of Greycoat21

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?