?
Solved

count the height of a tree

Posted on 2000-04-15
1
Medium Priority
?
226 Views
Last Modified: 2010-04-16
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
 
Please explain in details
0
Comment
Question by:adrianmak
1 Comment
 
LVL 2

Accepted Solution

by:
yairy earned 60 total points
ID: 2720464
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

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In-App Messaging has revolutionized the way we look at marketing. It has also changed the way we use Apps. If In-App Messaging is used well then you will find that it can drive a lot of traffic to specific areas of your site. It also helps to improv…
In this age of digitization where the online market is increasingly becoming competitive each day, I’ll give you the truth bomb: simply putting your business out there is not enough. Sure, you’ve got impressive content and interesting graphic design.
The Relationships Diagram is a good way to get an overall view of what a database is keeping track of. It is also where relationships are defined. A relationship specifies how two tables connect to each other. As you build tables in Microsoft Ac…
In this video I will demonstrate how to set up Nine, which I now consider the best alternative email app to Touchdown.

589 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question