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]

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.)

 

[Keith Thompson]

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.

 

[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
--
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]

# 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.

 

[Julian V. Noble]

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
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
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]

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