Using recursion to dispose of binary tree and free its memory

http://www.awitness.org/delphi_pascal_tutorial/source/dispose_binary_tree.html

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  link=^node;
  node=record keyname:string;  l, r:link end;
  TForm1 = class(TForm)
    Memo1: TMemo;
    Edit1: TEdit;
    AddButton: TButton;
    DestroyButton: TButton;
    ShowTreeButton: TButton;
    procedure FormCreate(Sender: TObject);
    procedure AddButtonClick(Sender: TObject);
    Procedure TreeInsert(keytext:string; q:link);
    procedure ShowTreeButtonClick(Sender: TObject);
    Procedure PrintTree(q:link);
    procedure DestroyButtonClick(Sender: TObject);
    procedure DestroyTree(q:link);
    procedure FormShow(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  head, tail:link;
implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
begin
Memo1.Lines.Clear;
Edit1.Text:='';
new(tail); new(head);
head^.keyname:=''; head^.r:=tail;  head^.l:=tail;
end;



procedure TForm1.AddButtonClick(Sender: TObject);
begin
     If Edit1.Text<>'' then begin
        TreeInsert(Edit1.Text, head);
        Edit1.Text:='';
     end;
     Edit1.SetFocus;
end;

{nodes are inserted as leafs (both binary pointers are dead ends - so search to the left
if new key is less than current key, or search to the right if its greater until a dead end
is reached - signified by the tail pointer which is similar to 'nil' pointer
then attached the leaf (with both pointers set to nothing) as a leaf on the tree, either
on the left, if less than attachment node key value, or on the right if greater}

Procedure TForm1.TreeInsert(keytext:string; q:link);
var st:link;
begin
repeat
      st:=q;
      if keytext<q^.keyname then q:=q^.l else q:=q^.r;
until q=tail;
new(q); q^.keyname:=keytext;
q^.l:=tail; q^.r:=tail;
if keytext<st^.keyname then st^.l:=q else st^.r:=q;
end;


procedure TForm1.ShowTreeButtonClick(Sender: TObject);
begin
Memo1.Lines.Clear;
PrintTree(head);
end;

{tree is sorted, so traverse all the way to the left (find least value} and then as it returns
from each node, print out (in sorted order) and check for a node on right pointer - this 
performs an in order printout of a sorted tree}

Procedure Tform1.PrintTree(q:link);
begin

     if q<>tail then begin
        PrintTree(q^.l);

        Memo1.Lines.Append(q^.keyname);

        PrintTree(q^.r);
     end;
end;

{the head is set to nothing '' string so to avoid destroying the head, begin tree destruction
from the 'right' pointer of the head which is where the first value was inserted onto tree
remember to set head to dead end pointer on return}

procedure TForm1.DestroyButtonClick(Sender: TObject);
begin
DestroyTree(head^.r);
head^.r:=tail;
Edit1.SetFocus;
end;

{completely traverse the tree using a recursive call, and as each returns it will destroy
the nodes in the correct order, freeing up the memory of the binary tree}

procedure TForm1.DestroyTree(q:link);
begin
     if q<>tail then begin
        DestroyTree(q^.l);
        DestroyTree(q^.r);
        Memo1.Lines.Append('Destroying ' + q^.keyname);
        Dispose(q);


     end;
end;
procedure TForm1.FormShow(Sender: TObject);
begin
Edit1.SetFocus;
end;

end.