Binary tree from unsorted array

Question

I have an array of records from which I am trying to construct a binary tree. The end result should be as follow. -1 represents null and if both the left and right pointer are -1, it is a leaf node.

| Index | Left Pointer | Data | Right Pointer |
|:-----:|:------------:|:----:|:-------------:|
|   0   |       1      |  17  |       4       |
|   1   |       2      |   8  |       3       |
|   2   |      -1      |   4  |       7       |
|   3   |      -1      |  12  |       6       |
|   4   |       5      |  22  |       8       |
|   5   |      -1      |  19  |       -1      |
|   6   |      -1      |  14  |       -1      |
|   7   |      -1      |   5  |       -1      |
|   8   |       9      |  30  |       -1      |
|   9   |      -1      |  25  |       -1      |

This is my current code:

type node = record
    data : string;
    left : integer;
    right : integer;
end;

var
  binaryTree : array[0..9] of node;

procedure output;
var
    i : integer;
begin
    for i := 0 to 9 do
    begin
        writeln('Data: ' , binaryTree[i].data);
        writeln('Left: ' , binaryTree[i].left);
        writeln('Right: ' , binaryTree[i].right);
    end;
end;

procedure takeInput;
var
    i : integer;
begin
    for i := 0 to 9 do
        readln(binaryTree[i].data); 
end;

procedure initialisePointers;
var 
    i : integer;
begin
    // initialise to -1 for null
    for i := 0 to 9 do
    begin
        binaryTree[i].left := -1;
        binaryTree[i].right := -1;
    end;
end;

procedure setPointers;
var
    i : integer;
    root, currentNode : node;
begin
    // first value becomes root
    root := binaryTree[0];
    for i := 1 to 9 do
    begin
        currentNode := root;
        while true do
        begin
            if binaryTree[i].data < currentNode.data then
            begin
                if currentNode.left = -1 then
                begin
                    currentNode.left := i;
                    break;
                end
                else
                    currentNode := binaryTree[currentNode.left]
            end
            else
            begin
                if binaryTree[i].data >= currentNode.data then
                begin
                    if currentNode.right = -1 then
                    begin
                        currentNode.right := i;
                        break;
                    end
                    else
                        currentNode := binaryTree[currentNode.right]
                end;
            end;
        end;
    end;
end;

begin
    takeInput;
    initialisePointers;
    setPointers;
    output;
end.

With the input shown in the table, I get an output of all pointers remaining at -1 as initialised. Any idea why this may be?

500 - Internal Server Error · Accepted Answer · 2018-10-25 16:48:58Z

1

In Pascal, records are value types, so when you do e.g.

root := binaryTree[0];

then root is a copy of binaryTree[0].

When you set fields in root you are setting fields in the copy.

If you want chose changes reflected back in the binaryTree array, you have to assign the value back after use:

binaryTree[0] := root;

Or else, use pointers, but I am not sure you have learned about those yet.

answered Oct 25, 2018 at 16:48

500 - Internal Server Error

29k8 gold badges64 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Habib C Over a year ago

Thanks, I understand what the issue is now. But could you please point out where exactly I need to add this.

500 - Internal Server Error Over a year ago

The simplest way to fix your current code is probably going to be eliminating the locals root and currentNode in setPointers. Instead, use indexes into binaryTree.

Collectives™ on Stack Overflow

Binary tree from unsorted array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related