Solved

count the height of a tree

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

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

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

Suggested Solutions

This article outlines why you need to choose a backup solution that protects your entire environment – including your VMware ESXi and Microsoft Hyper-V virtualization hosts – not just your virtual machines.
As a business owner, there are many things that keep you up at night. Profit margins, employee retention, human resource protocols, whether your product or service will remain competitive. When you own or manage a technology company that operates la…
This Micro Tutorial will teach you how to censor certain areas of your screen. The example in this video will show a little boy's face being blurred. This will be demonstrated using Adobe Premiere Pro CS6.
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …

809 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