How to determine the height of a binary tree

TDR

Delphi Developer

Wed, 18 Jun 1902 08:00:00 GMT

How to determine the height of a binary tree

Hi,
Can anyone here help me? Our class was given a homework to write a recursive
function that can determine the height of binary (standard Binary tree ADT).
And so far, I haven't been able to do the function as I just can't seem to
figure out the logic of writing the recursive function. So I would really
appreciate it if someone could tell me the algorithm for solving this
problem(or better provide me with the source codes !) or at least show me
where I can find some info on solving this problem

TDR

Osmo Ronkan

Delphi Developer

Wed, 18 Jun 1902 08:00:00 GMT

Re:How to determine the height of a binary tree

Quote

In article <382588a...@news.tm.net.my>, TDR <tdr_jo...@hotmail.com> wrote:
>Hi,
>Can anyone here help me? Our class was given a homework to write a recursive
>function that can determine the height of binary (standard Binary tree ADT).
>And so far, I haven't been able to do the function as I just can't seem to
>figure out the logic of writing the recursive function. So I would really
>appreciate it if someone could tell me the algorithm for solving this
>problem(or better provide me with the source codes !) or at least show me
>where I can find some info on solving this problem

Function Height(p:node):word;
var l,r:word;
Begin
if p=nil then begin
Height:=1;
exit;
End;
l:=height(p^.left);
r:=height(q^.right);
if r<l then Height:=r
else Height:=l;
End;

The above code has a few deliberately inserted errors so you have to
figure how it works before presenting it.

A general principle of a recursive routine is:

1) check for the termination condition
2) call the function recursively with modified parameters one or more times
3) process the results of the recursive calls.

Osmo

Ingmar Tulv

Delphi Developer

Wed, 18 Jun 1902 08:00:00 GMT

Re:How to determine the height of a binary tree

In article <8046m6$k8...@kruuna.Helsinki.FI>,
ronka...@cc.helsinki.fi (Osmo Ronkanen) wrote:

Quote

> Function Height(p:node):word;
> var l,r:word;
> Begin
> if p=nil then begin
> Height:=1;

Why not 0?

Quote

> exit;
> End;
> l:=height(p^.left);
> r:=height(q^.right);

Mm..
l:=height(p^.left)+1;
r:=height(p^.right)+1;
Did you mean this?

Quote

> if r<l then Height:=r
> else Height:=l;
> End;

Well, what is height of a binary tree? I guess it should be 'if r>l' but
this can be discussed.

Quote

> The above code has a few deliberately inserted errors so you have to
> figure how it works before presenting it.

> A general principle of a recursive routine is:

> 1) check for the termination condition
> 2) call the function recursively with modified parameters one or more
times
> 3) process the results of the recursive calls.

> Osmo

4) check for bugs :-)

(I do not guarantee that I didn't add any)

Ingmar

Sent via Deja.com http://www.deja.com/
Before you buy.

Sebastian Koppeh

Delphi Developer

Wed, 18 Jun 1902 08:00:00 GMT

Re:How to determine the height of a binary tree

Hi,

on Sun, 07 Nov 1999 at 14:13:10 o'clock, TDR wrote:

Quote

> Can anyone here help me? Our class was given a homework to write a recursive
> function that can determine the height of binary (standard Binary tree ADT).
> And so far, I haven't been able to do the function as I just can't seem to
> figure out the logic of writing the recursive function.

For any given node, the height of the tree on top of which it sits is one
plus the height of the trees under it (if they are not equal in height,
take the greater one).

That should pretty much explain it, because it is a recursive definition,
and if you start with the tree's root, the height you calculate from there
is the height of the whole tree.

- Sebastian

--
Always remember: "Batch" is NOT a programming language!

Osmo Ronkan

Delphi Developer

Wed, 18 Jun 1902 08:00:00 GMT

Re:How to determine the height of a binary tree

In article <804f95$fo...@nnrp1.deja.com>,
Ingmar Tulva <mi...@my-deja.com> wrote:

Quote

>In article <8046m6$k8...@kruuna.Helsinki.FI>,
> ronka...@cc.helsinki.fi (Osmo Ronkanen) wrote:

>> Function Height(p:node):word;
>> var l,r:word;
>> Begin
>> if p=nil then begin
>> Height:=1;

>Why not 0?

>> exit;
>> End;
>> l:=height(p^.left);
>> r:=height(q^.right);

>Mm..
> l:=height(p^.left)+1;
> r:=height(p^.right)+1;
>Did you mean this?

>> if r<l then Height:=r
>> else Height:=l;
>> End;

>Well, what is height of a binary tree? I guess it should be 'if r>l' but
>this can be discussed.

>> The above code has a few deliberately inserted errors so you have to

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quote

>> figure how it works before presenting it.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quote

>> A general principle of a recursive routine is:

>> 1) check for the termination condition
>> 2) call the function recursively with modified parameters one or more
>times
>> 3) process the results of the recursive calls.

>> Osmo

> 4) check for bugs :-)

Well you found all the bugs I inserted. Now you gave the guy his
homework.

Osmo

Ingmar Tulv

Delphi Developer

Wed, 18 Jun 1902 08:00:00 GMT