# Board index » delphi » Problem with recursion and binary search trees

## Problem with recursion and binary search trees

I'm having a problem with recursion.  I'm trying to create a function that will
return the number of interior nodes in a binary search tree (bst) not including
the root node.  The function below returns the number of interior nodes
including the root node but I can't figure out how to modify it so that it won't
include the root node.  Can anybody help me?  I would appreciate it a lot.

type
bst = ^bstnode;
bstnode = record
number: integer;
leftptr: bst;
rightptr: bst;

{returns the number of interior nodes in the binary search tree not including
the root node}
function interior(bst1: bst): integer;

begin
if bst1 = nil then
interior := 0
else if (bst1^.leftptr = nil) and (bst1^.rightptr = nil) then
interior := 0
else if (bst1^.leftptr <> nil) or (bst1^.rightptr <> nil) then
interior := 1 + interior(bst1^.rightptr) + interior(bst1^.leftptr)
end; {interior}

Edwin Wong
umwon...@cc.umanitoba.ca

## Re:Problem with recursion and binary search trees

##### Quote
Edwin Wong wrote:
> I'm having a problem with recursion.  I'm trying to create a function that will
> return the number of interior nodes in a binary search tree (bst) not including
> the root node.  The function below returns the number of interior nodes
> including the root node but I can't figure out how to modify it so that it won't
> include the root node.  Can anybody help me?  I would appreciate it a lot.

Why not just subtract one from the result?

- Rich

## Re:Problem with recursion and binary search trees

##### Quote
In article <4rfdlc\$...@canopus.cc.umanitoba.ca>, umwon...@cc.umanitoba.ca (Edwin Wong) writes:
> I'm having a problem with recursion.  I'm trying to create a function that will
> return the number of interior nodes in a binary search tree (bst) not including
> the root node.  The function below returns the number of interior nodes
> including the root node but I can't figure out how to modify it so that it won't
> include the root node.  Can anybody help me?  I would appreciate it a lot.

> [...]

Just subtract 1 from the result if the root node is <> nil...

Like this :

result=interior(mybst);
if result>0 then Dec(result);

The only problem is that you have to do this externally, but you can always
make another function that contains just the code above.

--
i3100...@univ.trieste.it
http://www.geocities.com/SiliconValley/8682/

## Re:Problem with recursion and binary search trees

In article <4rfdlc\$...@canopus.cc.umanitoba.ca>,

##### Quote
Edwin Wong <umwon...@cc.umanitoba.ca> wrote:
>I'm having a problem with recursion.  I'm trying to create a function that will
>return the number of interior nodes in a binary search tree (bst) not including
>the root node.  The function below returns the number of interior nodes
>including the root node but I can't figure out how to modify it so that it won't
>include the root node.  Can anybody help me?  I would appreciate it a lot.

>type
>bst = ^bstnode;
>bstnode = record
>                number: integer;
>                leftptr: bst;
>                rightptr: bst;

>{returns the number of interior nodes in the binary search tree not including
>the root node}
>  function interior(bst1: bst): integer;

>  begin
>    if bst1 = nil then
>      interior := 0
>    else if (bst1^.leftptr = nil) and (bst1^.rightptr = nil) then
>      interior := 0

Put 1 in above or just remove the thing as it is not necessary, the
first 'if' will take care of the ending of the recursion.

##### Quote
>    else if (bst1^.leftptr <> nil) or (bst1^.rightptr <> nil) then
>      interior := 1 + interior(bst1^.rightptr) + interior(bst1^.leftptr)
>  end; {interior}

If you'll get the number of all nodes. If you do not want to count the
root, just subtract one.

##### Quote

>Edwin Wong
>umwon...@cc.umanitoba.ca

Osmo