Non-recursive algorithm to find the height of a BInary Tree

[Ravi]

Hi,

I need to find the non-recursive algorithm to find the height of a
Binary Tree.

Regards,
SunLight.

[Walter Roberson]

In article <11************ **********@g14g 2000cwa.googleg roups.com>,
Ravi <ra********@per sistent.co.in> wrote:

I need to find the non-recursive algorithm to find the height of a
Binary Tree.

Any recursive algorithm can be converted to a non-recursive algorithm
(possibly requiring dynamic storage allocation for the implementation. )
--
"Who Leads?" / "The men who must... driven men, compelled men."
"Freak men."
"You're all freaks, sir. But you always have been freaks.
Life is a freak. That's its hope and glory." -- Alfred Bester, TSMD

[Keith Thompson]

"Ravi" <ra********@per sistent.co.in> writes:

I need to find the non-recursive algorithm to find the height of a
Binary Tree.

Good luck with that. Did you have a question?

The fact that you need a non-recursive algorithm strongly implies that
this is homework. We won't do your homework for you.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Emmanuel Delahaye]

Ravi wrote on 22/08/05 :

I need to find the non-recursive algorithm to find the height of a
Binary Tree.

Fine. Just tell us how is this a C question ?

Try news:comp.progr amming

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

"There are 10 types of people in the world today;
those that understand binary, and those that dont."

[SM Ryan]

"Ravi" <ra********@per sistent.co.in> wrote:
# Hi,
#
# I need to find the non-recursive algorithm to find the height of a
# Binary Tree.

Unless the tree is height balanced or threaded, you're going to be
doing an effectively recursive traversal anyway.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Haven't you ever heard the customer is always right?

[Julian V. Noble]

Ravi wrote:

Hi,

I need to find the non-recursive algorithm to find the height of a
Binary Tree.

Regards,
SunLight.

According to Kruse, "Data Structures & Program Design" any recursive
algorithm can be converted to a non-recursive one, by theorem. However,
the proof is not constructive, so there is no guidance for specific cases.
This is why CS, like mathematics, has an element of art.

--
Julian V. Noble
Professor Emeritus of Physics
jv*@lessspamfor mother.virginia .edu
^^^^^^^^^^^^^^^ ^^^
http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the
toothache patiently."

-- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.

[Richard Tobin]

In article <43************ ***@virginia.ed u>,
Julian V. Noble <jv*@virginia.e du> wrote:

According to Kruse, "Data Structures & Program Design" any recursive
algorithm can be converted to a non-recursive one, by theorem.

Though true, this is not generally useful, since you will typically
have to use something equivalent to a stack.

In the case of tree-traversal algorithms, it is sometimes possible to
use the tree itself instead of a stack, using "pointer reversal"
tricks. In years gone by garbage collectors often used this trick
(and perhaps they still do).

-- Richard