Linked Lists & Recursions, Part 2

BINARY TREE

If you have followed me this far, we come to the reason I wrote the article. A binary tree is an excellent way to store large amounts of alphabetical or numeric data since the functions INSERT (of new data) and LOCATE (of existing data) are so fast. A binary tree of numbers looks like this:

One number is designated as the root. Ideally, this number would be about the midpoint of all following numbers. All smaller numbers are to the left of the root, larger to the right. Numbers following the root are called nodes (25,40,100,..are nodes). Numbers at the end of a branch are called leafs (17,32,38,..are leafs.).

To insert a new number, one first decides if it is smaller or larger than the root.(If equal numbers can happen, they are usually sent to the right.) For smaller numbers, one travels down the tree to the left, making a decision at each node to go left or right. To insert 27, one goes left from 50, right at 25, left at 40, left at 30 and presto! a blank spot for 27.

To locate 26, one would travel the same route, looking left at 27 to find a blank. 26 is not in the tree since it could not be located at any other spot. For the function LOCATE, a tree is much faster than a linear search.

Remember that trees are not limited to numbers but could easily be names, cities, hobbies,… A computer knows that Carl is less than Mike, at least in the alphabet.

A binary tree can be stored in an array, but one quickly runs out of available memory since space must be available for every possible input. As you may suspect, a binary tree is a natural for a linked list with minimum storage requirements and almost instantaneous INSERT and LOCATE. DELETE is somewhat of a problem, but, in general, one connects the lower part of the tree to the node above-bypassing the deleted node. Through short recursive programs, one can print the tree in several different orders. Three commonly used orders are:

IN ORDER In numerical or alphabetical order.

PRE ORDER, POST ORDER Pre and Post order are used for special searches, restoring an ordered tree for storage, simulating algebraic operations,…

Let’s first examine linked list storage for a BASIC binary tree:

max        Estimated maximum number of data items.
d(max)     Incoming data.
l(max)     Left pointer.
r(max)     Right pointer.

I	D(I)	L(I)	R(I)
1	50	2	5
2	25	4	3
3	40	6	0
4	10	0	8
5	100	7	9
6	30	0	10
7	70	12	0
8	15	0	11
9	150	0	0
10	35	15	13
11	20	14	0
12	60	0	16
13	38	0	0
14	17	0	0
15	32	0	0
16	65	0	0

For the tree in the sketch above, incoming data could be: 50,25,40,10,100,30,70,15,150,35,20,60,38,17,32,65. For the root 50, the left pointer is line item 2 (25) and the right pointer is line item 5 (100). From 100, we can see the left pointer is item 7 (70) and the right pointer is item (150).[^item9] Item 9 is a leaf since there is no left or right pointers.

LOCATE A subroutine for LOCATE with input N, returns with:

Found=1 if N is in the tree.
Found=0 if N is not found.
i is the index of the parent node if N is not found.

LOCATE Subroutine[^wrap]

290 REM ..SR LOCATE..
300 LET Found=0: LET i=1
310 IF d(i)=0 THEN PRINT"Tree is empty.": RETURN
320 IF N=d(i) THEN LET Found=1: RETURN
330 IF N>d(i) THEN GO TO 360
335 REM Left side
340 IF l(i)=0 THEN RETURN
350 LET i=l(i): GO TO 320
355 REM Right side
360 IF r(i)=0 THEN RETURN
370 LET i=r(i):GO TO 320

To locate 27 in preparation for INSERT, the LOCATE routine would look at (See Fig 4)[^fig4] line 1, line 2, line 3, line 6 and then return with Found=0 and i=6, which would be the node just preceding an insert of 27.

For INSERT, 27 would go on line 17 as a new entry and pointer l(6) is changed to 17.

IN ORDER, I once tried an array representation for a binary tree where a spot is open for every possible entry into the tree (See sketch at left). The problem was to write a subroutine for IN ORDER. After going through page after page, I finally decided that I didn’t have the ability to do it. (Actually, I decided that it couldn’t be done.) Using recursion with a linked list, IN ORDER can b written in 5 lines. Input is i=1.

IN ORDER Subroutine

490 REM ..SR IN ORDER..
500 IF d(i)=0 THEN RETURN
510 GOSUB PUSH: LET i=l(i): GOSUB IN ORDER
520 GOSUB POP: PRINT d(i);", ";
530 GOSUB PUSH: LET i=r(i): GOSUB IN ORDER
540 GOSUB POP: RETURN

Follow the routine above for just small branch of the tree in Fig 3. Remember that a RETURN sends you back to the most recent GOSUB (either line 510 or 530). PUSH and POP save and return the index i.

1. The routine walks down the left side, storing the i values for 50, 25, 10, until l(i) of 10 is found as 0.
2. The i for 10 is popped and d(i)=10 is printed.
3. The i for 10 is pushed and the right side is examined.
4. No left side for 15, so d(i)=15 is printed.
5. The right side is examined and a left side is found (ie statements 500, 510 say l(i)<>0)
6. The left side is chased down, l(i)=0 is found and d(i)=17 is printed.
7. With a return from 510, d(i)=20 is printed.
8. The next pop & return prints d(i)=25 and the program continues. For just five lines, the program is busy, busy, busy.

This is recursion at its best. If you would like to examine a binary tree further, the program Binary Tree is in the SEATUG Library. The MENU includes INSERT, DELETE, LOCATE, Print Node List, PRINT Tree, IN ORDER, PRE ORDER, POST ORDER, Form Tree with RND, Form Tree with ENTER. Look for opportunities to use Linked Lists and Recursion in your programming. They can make your program more compact and make BASIC programming more fun.