Pascal changing recursion to while loop with pointer

Question

Hi I'm learning pascal and testing some functions
I made a recursive insert procedure like this. if node exist compare two keys, and if not, make a room for new node.

procedure INSERT (KEY : integer; var NODE : NODEPTR);
begin 
    if NODE = Nil then  
    begin
        New (NODE); 
        NODE^.KEY := KEY; 
        NODE^.LEFT  := Nil;
        NODE^.RIGHT  := Nil
    end
    else            
        if KEY < NODE^.KEY then
            INSERT (KEY, NODE^.LEFT)
        else
            INSERT (KEY, NODE^.RIGHT)   
end;

and What I'm trying to do is changing recursive function to while-loop. so I made procedure like this
if node exist do while loop until node is empty. and after while loop is over, make a new node

procedure INSERT (KEY : integer; var NODE : NODEPTR);
begin 
    while NODE <> nil do
    begin
        if KEY < NODE^.KEY then
            NODE:=NODE^.LEFT
        else
            NODE:=NODE^.RIGHT
    end;

    New (NODE); 
    NODE^.KEY := KEY; 
    NODE^.LEFT  := Nil;
    NODE^.RIGHT  := Nil

end;

when first node is root, while loop is true and execute this code but after this, while loop changes to false and make a new node.

        if KEY < NODE^.KEY then
            NODE:=NODE^.LEFT
        else
            NODE:=NODE^.RIGHT

Eventually there is no node connection, and this program just keep making new node.
Is there anything that i missed? or any improvising about the second code? thanks in advance :)

Willem van Rumpt Willem van Rumpt · Accepted Answer · 2012-12-12T08:50:30

The thing you missed is that you never link up the nodes (and in the current setup, you can't actually linkup the nodes). You have fields on your record for the left and right node of a node, but you don't assign them. So you end up just creating nodes without every linking them up; you have a linked list with the links missing.

At one point, you'll need something along the lines of NODE^.RIGHT := NEWNODE (or NODE^.LEFT := NEWNODE, of course).

You'll need something along the ways of (my Pascal is a bit rusty, so beware of syntax errors ;) ):

    procedure INSERT(key: Integer; var NODE: NODEPTR)
    begin
        NODEPTR root := NODE;
        if (key < root^.KEY) then begin
            while (root^.LEFT <> nil) do begin
                root := root^.LEFT;
            end;
            new(NODE);
            NODE^.KEY := key;
            root^.LEFT := NODE;
            node^.RIGHT := root;
        end else begin
            while (root^.Right <> nil) do begin
                root^ := root^.RIGHT;
            end;
            new(NODE);
            NODE^.KEY := key;
            root^.RIGHT := NODE;
            NODE^.LEFT := root;
        end;
    end;

There's lots of improvements and beautifications to be made in the example above, but I think it shows the general idea.

Pascal changing recursion to while loop with pointer

1 Answers