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

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.

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

      procedure AddNode(Item: string);

    public
      property Data: String read FItem;

      constructor Create(Items: array of String);

      destructor Destroy; override;

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

  end;

implementation

{ TBinarySearchTree }

procedure TBinarySearchTree.AddNode(Item: string);
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
      FLeft.AddNode(Item)
  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
      FRight.AddNode(Item);
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
      AddNode(Items[Index]);
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.

Community comments

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

dgeiger's Reflection

It's a lot easier to make a binary tree using classes than the old way of using records and pointers.