x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 226

# count the height of a tree

I have a function that count the height of a tree

function countheight(root:tree):integer;
var left, right:integer;
begin
if root=nil then countheight:=0
else
begin
left:=countheight(root^.left);
right:=countheight(root^.right);
if left>right then countheight:=1+left
else countheight:=1+right
end;
end;

I don't know the IF condition so it can calculate the height of a tree

0
1 Solution

Commented:
this is a recursive function.

It says that the the hight of the tree is the hight of the left sub-tree+1 (if the left sub-tree is higher then the right sub-tree)
OR
the hight of the tree is the hight of the right sub-tree+1
(if the right  sub-tree is higher the the left one)

Now, how do we know  what sub-tree is higher ?

we will RECURSEVLY treat each sub-tree as a tree.

example:

8
3       11
30

hight(8)=max(hight(3),hight(11))+1
hight(3)=max(hight(NULL), hight(NULL))+1
hight(NULL)=0  // ending condition
==> hight(3)=0+1=1.

hight(11)=max(hight(NULL), hight(30))+1
hight(NULL)=0
hight(30)=max(hight(NULL), hight(NULL))+1
hight(NULL)=0
==> hight(30)=0+1=1
==> hight(11)=1+1=2
==> hight(8)=2+1 = 3

as you can see, the recursion goes 'backwards'
with the result back to the first call...

Any questions,
Yair

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.