Solved

count the height of a tree

Posted on 2000-04-15
1
200 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 20 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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Never store passwords in plain text or just their hash: it seems a no-brainier, but there are still plenty of people doing that. I present the why and how on this subject, offering my own real life solution that you can implement right away, bringin…
In  today’s increasingly digital world, managed service providers (MSPs) fight for their customers’ attention, looking for ways to make them stay and purchase more services. One way to encourage that behavior is to develop a dependable brand of prod…
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.

705 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now