By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,016 Members | 2,297 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,016 IT Pros & Developers. It's quick & easy.

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

P: n/a
Hi,

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

Regards,
SunLight.

Nov 15 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
In article <11**********************@g14g2000cwa.googlegroups .com>,
Ravi <ra********@persistent.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
Nov 15 '05 #2

P: n/a
"Ravi" <ra********@persistent.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_Keith) 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.
Nov 15 '05 #3

P: n/a
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.programming

--
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."
Nov 15 '05 #4

P: n/a
"Ravi" <ra********@persistent.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?
Nov 15 '05 #5

P: n/a
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*@lessspamformother.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.
Nov 15 '05 #6

P: n/a
In article <43***************@virginia.edu>,
Julian V. Noble <jv*@virginia.edu> 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
Nov 15 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.