Binary Tree Help

Okay, I finally got most of my records program to work.  It saves an array
of records to a file, where-in I can reload all the records.  I can also delete
and reuse records. Now, here comes the fun part of my project: I have to
use binary trees in it.  The teacher wants the program complex.  So, I was
wondering how to attempt this.  The whole point of a binary tree is to cut
down search time, so I need to save it in a tree like form.  And since I
am saving it to a file, I think arrays would be much easier to use.

I do have some source code with binary trees, but all of them use
pointers, which I cannot save to a regular file.  So, what I need is
help or source code for the following:

1. Binary Tree that can sort records.  I have one that can sort
     numbers, but I need one that can sort records.  It also needs
     to add the record to the tree every time I enter a new record.
2. Can save the binary tree of records in an array format that can
     be loaded for immediate search.  I was thinking of just having
     a list of records and then add them to the tree before the search,
     but that would increase execution time and defeat the purpose
     of a binary tree.  If a binary tree that uses pointers can be saved
     to a file, I'm take a look at that too.  It doesn't have to be arrays,
     I just that it would be easier using them.
3. Have complete deleting routines: leaf, root, and middle. Deleting
    a leaf is pretty easy I guess.  It's the root and middle that makes it
    a pain in the butt.

Because I am asking a lot, I am giving 1100 points to the person that
helps me the most.
My rough source code for my project is at
You may take a look at it and offer suggestions.

Thank you!
LVL 23
Adam LeinssServer SpecialistAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

I'll post this first as a comment, cause it'll probably need a little more help to finish this, but this is what I propose firstly.

First, I'd build the BINARY-TREE support into your record. like this:

myrecord = record
  data : string  {or whatever};
  parent : word;
  children : array[1..2] of word;{or 1..whatever}

then you're VAR statement is something like this.
myvar : array[1..100] of record;

Then you can put the value "0" in the CHILDREN or PARENT area to indicate if the record is the ROOT, OR LEAF of the tree.

like in this tree.
                            R2    R3
                          R4 R5  R6 R7

where R1 is root
R2's parent is R1 its children are R4 and R5.
R3's parent is R1, its children are R6 and R7.
R4 and R5's parent is R2, and they each have NO children.
R6's parent is R3. It also has NO children.
R7's parent is R3, its only child is R8.

Here's how to set up this tree:
myvar[1].parent := 0;   {Has NO parents,therefore, it's the root}
myvar[1].children[1] := 2; {child 1 is record #2 -- myvar[2])
myvar[1].children[2] := 3; {child 2 is record #3 -- myvar[3]}

myvar[2].parent := 1; {parent is myvar[1]}
myvar[2].children[1] := 4;
myvar[2].children[1] := 5;

myvar[3].parent := 1;
myvar[3].children[1] := 6;
myvar[3].children[2] := 7;

myvar[4].parent := 2;
myvar[4].children[1] := 0; {0, therefore, NO CHILDREN};
myvar[4].children[2] := 0; {still no children};

Myvar[5].parent := 2;
myvar[5].children[1] := 0;
myvar[5].children[2] := 0;

myvar[6].parent := 3;
myvar[6].children[1] := 0;
myvar[6].children[2] := 0;

myvar[7].parent := 3;
myvar[7].children[1] := 8; {it has at least 1 child}
myvar[7].children[2] := 0; { has NO second child}

myvar[8].parent := 7;
myvar.children[1] := 0;
myvar.children[2] := 0;

Ok.. let me know if this still makes sense.. Implement this into your program, and let me know the remaining problems...
This should get the Tree into memory, and onto the disk. Now, transversing the tree, will be the next problem, we'll work on this after you post the next problems you have .
Adam LeinssServer SpecialistAuthor Commented:
Well, I see how you constructed the tree.  That makes sense.  However, if I was entering
in a record, there would be no way of comparing them in a flat line of 100 records (
that's probably what you mean by transversing the tree, which you didn't get to yet).  I was thinking of an array like this:

  1        2       3
1 3   Record    2

2 5   Record    7

3  9  Record    8

So, the root's left child pointer would point to array number 3, its left child, etc.  In
this way, the triunal array would be setup like this:

Pointer to Left Child/Record/Pointer to Right Child

If we were sorting numbers, the code would look something like this:

procedure addnode(data: longint);

var cnt, num, flag: longint;

   cnt := 2;
   num := 1;
   flag := 1;
   while (flag = 1) do
      if (data > tree[num, 2]) then
         if (tree[num, 3] = 0) then
            tree[last, 2] := data;
            tree[last, 4] := cnt;
            if not(last = 1) then tree[num, 3] := last
            else tree[last, 4] := 1;
            last := last + 1;
            flag := 2;
            num := tree[num, 3];
            cnt := cnt + 1;
         if (tree[num, 1] = 0) then
            tree[last, 2] := data;
            tree[last, 4] := cnt;
            if not(last = 1) then tree[num, 1] := last
            else tree[last, 4] := 1;
            last := last + 1;
            flag := 2;
            num := tree[num, 1];
            cnt := cnt + 1;

I was figuring of adding the records like this.  I like your idea of adding "pointer" information to the record itself, but I don't see how you would input records and
sort them into the tree.

I'm gonna have to know what you're program is actually trying to do ( in plain english). Actually the part I'm needing to know is how your program needs to "sort" into the tree. How does it decide where in the program it needs to be?

Start there, explain it in english how the sort is to happen.

Note: Transversing the tree, is the art of "moving" (or searching) up and down the tree, doing a binary search if you will.

Cloud Class® Course: SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

You can implement the binary tree as records array by using this trick:

A binary tree have at most two childs.
So if your current cell is in the X's place of the array, put the children in the 2X and 2X+1 places.
In that way, you can find the father of tree-cell ( it will be in the |X/2| place) and its children (2X, 2X+1 as I mentioned earlier).
However, you should put the information if the left/right child of the cell is occupied.

As for sorting records, I don't know what you put inside your records. However, you have to write "Relation" or "Ordering" function that compares two items of your data structure. As you know, in binary tree (at least the ones I know), the left child is smaller than the father, and the right child is grater than the father, even if you dicide to insert fruits into the tree. Since during the insertion the structure should retain, you will use this function to get order of the records.

Now for deleting of item, you move the left child instead of the current cell, and for the child you trace by the right ones:

      7                    _             3            3
    3   8    delete(7)   3   8    -->  _   8   -->  4   8
   1 4 5 10             1 4 5 10      1 4 5 10     1 _ 5 10

Hope this is understandable...
If you still need "complete deleting routine" specify the data-record you are using and the implementation of the tree yuo decided to use.

Hope this was helpful
Adam LeinssServer SpecialistAuthor Commented:
jlove1: After I entered the information entered, I was then going to have
it insert it into the binary tree.

Pseudo code:
write ('Enter phone number: ');
             readln (phone);
            write ('Is this information correct? (Y/N)');
            readln (c);
           end {2nd while};
           if z = 1
             then x := newroot_bst(person)
              else insert_into_bst(person, x);
                write ('Add another entry? -> ');
                readln (addentry);

So, after I would enter the record in, it would transverse the tree and
look for a home. I did find a web page,,
that deals with binary trees and records, however, all of the procedures/fuctions use
pointers, which, I can't save to a file.  That's why I suggested arrays.  Let me know if this helps.

FuzzyLogic: Interesting equations!  I did work a tree by hand and that does work!  In
deleting, you always promote right, so in this tree

                  /        \
                 2         3
               /   \      /    \
             4     5   6     7              

if I wanted to delete 3, I would promote right and replace 3 with 7.  For 4, I would just
zero it out.  Why would you move the left child?

I noticed that you said that you were putting the data into a binary tree in order to speed up searches. I'll show you an example usage and an example tree. In the following example, it simply has some DATA sorted in order...... as so... (note: the numbers are values (DATA) and NOT record numbers within an array.) (the data is 1..25)

                          /               \
                           6                 18
                       /      \           /       \
                      3        9         15        21
                    /  \     /  \       /   \      /  \
                  1    5    7   11     13   17    19   23
                   \  / \    \  /     /  \  /  \    \  /  \
                   2 4  6    8 10    12 14 16  18  20 22  24

In the above tree, the values 1-25 were sorted into the tree. They were put into the tree so a search could locate the record in a low number of searches.
Say, you're looking for a record containing the number 16, you'd start searching the tree, and compare the value 16, to the ROOT (12)... You'd see that the number 16 is greater than 12, so you'd move to the RIGHT (less would be to the left).

so to FIND 16, you'd move RIGHT, LEFT,RIGHT,LEFT to find the value.

If you were searching, say for a number that doesn't exist, like 26, you'd keep moving right from the root until you reached the end and got to a point where no children existed.. then you'd know that you're done.

Now, if you wanted to delete the RECORD 15 from the tree above.. shown below..

                /     \
              13      17
             /  \    /  \
           12  14   16  18

There's SEVERAL ways to accomplish this task...
The first way would be to replace the 15 with the 17, and "hook" the 13 onto the 16. The resulting tree would be
            /      \
          16       18
       /  \
      12  14

The problem with this method is that you lose search efficiency, and the further UP the tree that the tree occurs, the more efficiency you lose.  

The second method is to totally rebuild the tree, but this could take a lot of time to delete records.

Second THIRD would be to to TOTALLY resructure that section of the tree.
Resulting in the following tree:
            /    \
          13     17
         /      /   \
       12      16   18

I'd reccomend the third method.. It's the best balance between speed and efficiency.

Implementing the THIRD method would be to copy every record "under" the record being deleted into a temp array, then arranging the temp array, and overwriting the old values in the old section of the main array. If this still doesn't make sense, I'll post some code.. but usually code is more "greek" than english. I Like explaining what I'm doing rather than just spitting out code.

let me know if this sounds implementable

In order to search a array of records, you can use binary search trees, using arrays of pointers. Using arrays to construct trees is a waste. The main concept behind this is to represent the parent node as i and the child nodes as 2i and 2i+1.
Hence the root node will be 1 and the child nodes will be 2 and 3. If your main aim is to do a fast search on the records then load the records on to an array and do a binary search on it. Searching using binary trees is very similar to binary search except that the records are stored as nodes in tree and are dynamic and hence do not depend on the no: of records.
Anyway, reading your 3 questions I find that representing the records in trees using Pointers will be the best.
Why ? Because your 1st question was to sort the records. This is simple in trees. Store the records in the Left, Right, or Middle of the parent node and the inorder traversal will give you the sorted records. Cool!.
Your second question was to save the records and retrive it. This is also very simple.
And the last one was tree deletion, this is really easy, and can be implemented using recursion in about 25 lines. If you would like to make the searching of trees more faster
you can implement AVL trees (by rotation the tree is balanced). If you find my answer convincing I can write the source code for you, for searching, storing, retriving, and deleting in Pascal.
Just reply to this if you want the source code. I will write it.
Santosh.. try reading before posting :-) you just plaigerized FuzzyLogic
Adam LeinssServer SpecialistAuthor Commented:
santhosh: Interesting.  So instead of having the pointer point to memory
locations, you would have them pointing to sections in the file?  Anyways,
if you can write the source code for for searching, storing, retriving, and deleting
records using binary trees and I like it (translation: it works! :)), I will give you the
points.  Again, it must be able to be saved to a file (otherwise, there would be
no point of it being a database!).  I can create binary trees with pointers, but
I am unsure how to save these to a file.

For the comparsion and tranversal, my idea is to have them sorted by name.
So, in this tree:

                                      /      \
                                Adam     Derek
                                 /    \        /     \
                           Carla   C.J.  Fred    Willy

If I entered a new record with the name of Joe, it would compare it to the root,
and transverse right, to Derek, to Willey, then pop back and "push" to Fred
and branch off of Fred.

jlove1:  I get some of the concepts like balancing, rebuliding, and inorder, preorder,
and postorder searches, I just don't know how to

Save pointer/binary tree/record information all at the same time to a file and
be able to retrieve it.

Because of this, I was going to use arrays, which santhosh said was a big no-no.
I kinda got it the binary tree to work with arrays, but I have no code to go by for
working with them (ok, I have some, but not a complete deleting rountine).  I
do have code with procedures and functions that deal with records that uses
pointers, however, I don't know how you would save these to a file.  Memory
and files are different and there-in lies my problem.  The project is do by May
21st, therefore, I don't have a lot of time and I don't want to program a binary
tree code from scratch (Windows 95/98 no doubt was not bulit from scratch,
otherwise, it would take 20 years to complete!).

My teacher's two requirements were:

1. Advanced Data Structure such as stacks, queues, binary trees, pointers,
linked lists, etc.  I choose to do a database program, because it seemed like
something I could do.
2. One Function

That's all the guidelines I got, so, I have to use binary trees in my project!
(It works quite nicely without them FYI!).  I bulit a binary tree program using
numbers, but it was not required that we save it to a file.  Also, we only did
2 of the 4 possible deleteing rountines.      

Binary Trees are complex and all I need to know how I can save pointer/tree/record
information to a file or source code that does it.
Adam LeinssServer SpecialistAuthor Commented:
Ok, this question is open to anyone.  I modfied a program that uses a binary tree
and records, using pointers.  It is at and
its included file,  This source code
is perfect!  However, I need it to save this information to a file.  I want to be
able to reload/delete/add things to tree and have it save it to the file.  So, if I delete
something off the tree, it will be deleted from the file, or the pointer to that record
will be destoryed.  So, go to the above web site. If you can write the source code
for reading/writing this information to the file, you will get 1100 points!
Adam LeinssServer SpecialistAuthor Commented:
This question is going to be re-opened to everyone.  (Read above message).  The total of 1100 points will be imparted to your account for your correct source code!!!!!!!  Leave
your source code in an answer or mail it to  The person who
submits the first working source gets a cool 1100 points (I've saved this amount over
8 months, it's worth it to me)!  My orginial question has been watered down, hopefully,
it will be easier to find a solution to.
Are you wanting to use "POINTERS?" or psudo-pointers.. the record pointing info that we discussed earlier... For example in his code....

    Rec_Ptr        =  ^Data_Record
    Rec_Id         = integer;
    Rec_Name       = string[25];
    Rec_Address    = string[30];
    Rec_City_State = string[20];
    Rec_Ssn        = string[11];
    Rec_Phone      = string[8];
    Data_Record = record
     id         : Rec_Id;
     name       : Rec_Name;
     address    : Rec_Address;
     city_state : Rec_City_State;
     ssn        : Rec_Ssn;
     phone      : Rec_Phone;
     LCtr, RCtr : integer;
     LPtr, RPtr : Rec_Ptr;

      end {record};

   storrec = array[1..10] of Data_Record;

the above would be replaced with
    Rec_Ptr        = INTEGER; {NOTE THIS CHANGE-- WE're using an INTEGER to achieve the same effect as a pointer}
    Rec_Id         = integer;
    Rec_Name       = string[25];
    Rec_Address    = string[30];
    Rec_City_State = string[20];
    Rec_Ssn        = string[11];
    Rec_Phone      = string[8];

    Data_Record = record
     id         : Rec_Id;
     name       : Rec_Name;
     address    : Rec_Address;
     city_state : Rec_City_State;
     ssn        : Rec_Ssn;
     phone      : Rec_Phone;
     LCtr, RCtr : integer;
     LPtr, RPtr : Rec_Ptr;

      end {record};

   storrec = array[1..10] of Data_Record;

Okay.. 1 change, and basicy the same from there on  in the declarations...

The CREATE NODE procedure will be DRASTICLY DIFFERENT in your program, as it will have to search the array for a "place" to put the new data.. basicly it's looking for a "blank" record. We'll use a 0 as a parant and each child being 0 to constitute a blank record.

like this:
Say your array was declared like this
mytype = record
   data : integer;
   parent : integer;
   child1 : integer;
   child2 : integer;

mytree : array[1..100] of mytype;

Having that out of the way, the Create_Node procedure would look something like this:

procedure create_node(temp : mytype);
a : integer;
a := 0

a := a + 1;
if a > 100 then {Your Array is FULL, declare a bigger array!}
until (mytree[a].parent = 0) and (mytree[a].child1 = 0) and (mytree[a]child2 = 0);
mytree[a] := temp;

Make any sense???

You can still use our above discussed method of using an array of records and save the file that way. Let me know if this helps, and whatever else you need rewritten..

To ZERO OUT a record, simply make it's parent 0 and it's children 0..

 It seems like a hack, but PKZIP and other major programs use this method.. I'm sure it can work for you.
Adam LeinssServer SpecialistAuthor Commented:
Well, I tried your method and it doesn't work.  You can't change any of the
pointers, otherwise, the program won't work.  I tried putting your part in
and leaving in your part, it still doesn't work.  There has to be some way????
Changing all the pointers would be a night mare.  Oh well.  Back to the
drawing board.  I keep working on it.
Aleinss, I'd try to be self-confident that you will like my answer. But if it doesn't satisfy you, don't hesitate to re-open the question :-)
Well, it's obvious to me that you're in a kind of deadline rush, so what you need is a file feature for your program. Here I'm offering a quick and *dirty* code to add the capability to save and load the entire tree. Sure it's not really nice to save and load the ENTIRE tree, it's more likely to be a kind of save game :-) But I got an impression that you don't want to screw up your code, so here's the code:

{ TREE2.INC - include this in after TREE.INC }
function FileExists(FileName: string): boolean;
var f: file;
  Assign(f, FileName);
  {$I-} Reset(f); Close(f); {$I+}
  FileExists := (IOResult = 0) and (FileName <> '');
end;  { FileExists }

procedure SaveTree(Root: Rec_Ptr);
const FileName = 'TREE';
var f: file of Data_Record;

  procedure Sub_save(Ptr: Rec_Ptr);
    if Ptr <> nil then begin
      Write(f, Ptr^);
  end;  { Sub_save }

  Writeln('saving tree');
  Assign(f, FileName + '.DAT');
  Writeln('saving finished.  press return'); Readln;
end;  { SaveTree }

procedure LoadTree(var Root: Rec_Ptr);
const FileName = 'TREE';
  f: file of Data_Record;
  temp: Data_Record;

  procedure Sub_load(var Ptr: Rec_Ptr);
    if not eof(f) then begin
      Read(f, Ptr^);
      if Ptr^.LPtr <> nil then Sub_load(Ptr^.LPtr);
      if Ptr^.RPtr <> nil then Sub_load(Ptr^.RPtr);
  end;  { Sub_load }

  if FileExists(FileName + '.DAT') then begin
    Writeln('loading tree');
    Assign(f, FileName + '.DAT');
    Writeln('loading finished.  press return');
  end else Writeln('file not found.  press return');
end;  { LoadTree }

and in your TREE.PAS
      writeln ('J : Save to file');
      writeln ('K : Load from file');
      case Option of
            'J' : SaveTree(Root);
            'K' : LoadTree(Root);
and another important thing, I noticed you misplaced the Mark procedure, you should use it in the very beginning, so I modified your program to be:
      Heap_Ptr     : pointer;
begin      {main program}
I have tested this new modified program and it works quite well.
To be honest, 1100 point is too big to be missed :-)
Looking forward to your response. Bye.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
I was really getting at a "method" rather than Plagerizing someone elses source code.. I was hoping to somehow guide, or teach you a method of accomplishing what your wanting, without actually doing your homework. I'll just get rid of the pointers using the source MYSELF. I know it can be done easily.. I'll post the source when I'm done.

One thing I DO NEED TO KNOW is This:
I've been asking this in my above posts, but I've never seen you answer.
I see that your putting in a BINARY TREE to speed up the searches. The only way that a tree can speed up a search is if it is laid out in a logical order..
What "order" are you wanting your tree to be in..
In other words, how is this tree to be sorted. All the source code in the world won't help until I know how this is needing to be done.
I saw you mention "sorting" a tree by name.. you mentioned the following tree..

                                            /      \
                                      Adam     Derek
                                       /    \        /     \
                                 Carla   C.J.  Fred    Willy

I did notice that you "named" each node by a NAME, but what is the order  in which they are put into the tree -- it doesn't look alphabetical.. is it based upon some other criteria?.
Let me explain this using your tree.. -- Then I'll rewrite your tree for higher efficiency.

Okay, here goes.
Say your program for some reason is trying to search YOUR tree for "C.J".
In your example, the computer would start at the root ("Bob") and start a methodical "blind" search.. until it finds "C.J".. this method would be LESS EFFICIENT than just cycling through the names in an array. for example, your program would first look at "BOB", then "ADAM", then "CARLA"-- well, it's at the end of the tree, and it has to start over.... of this tree were more optimized, it'd be DONE with the search.

it could have to look at all 7 records before it finds CJ (or any other search).

Consider if I arranged the tree in the following way:
                                            /         \
                                      Bob             Fred
                                       /    \             /      \
                                 Adam  Carla .  Derek  Willy

Here's where the time is saved: (especially in a HUGE tree)
The relationship here is where the name falls when ALPHABETIZED.
If you'll notice-- I arranged the tree so that No matter what happens, if you move down to the LEFT, you'll be moving "alphabeticly backwards" (from z to a) and if you move to the right, you're moving FOREWARDS.. (a to z)

Say, in this example, we're looking for "Derek"
The computer would start at the root ("CJ")
The computer sees that CJ is not "Derek" and continues the search...
It figures out that "Derek" falls Alphabeticly AFTER CJ, so it knows to move RIGHT.
So, it moves right and sees that "Fred" is not "Derek"
It figures out that  "Derek" falls Alphabeticly BEFORE "Fred", so it knows to move LEFT.
So It moves LEFT, and finds that "Fred" is in fact "Fred" and the search is OVER.
It had to search only 3 records to accomplish this task.

Now, the deal with this tree is that it has to be "rebuilt" every time that records are added in order to maintain the relationship.

What I need to know is WHAT KIND of relationship your tree will have? This is the MOST IMPORTANT THING in a binary tree. Without it, you gain NO efficiency, and only complicate (and slow down) your program.

Hopefully, I've explained this good enough so that you can post the needed info. I'll be happy to write the code necessary to achieve this feat, but I need to know what your searches are going to be based upon. Thank you.
Adam LeinssServer SpecialistAuthor Commented:
Wow, great code dude!  Works like a charm. Added an extra 100 points just
for ya! ;)  Thanks for jlove1 and all the others for the help.  I'm happy now!


It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.