473,324 Members | 2,178 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

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

Hi,

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

Regards,
SunLight.

Nov 15 '05 #1
6 11185
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
"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
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
"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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: klaus triendl | last post by:
hi, recently i discovered a memory leak in our code; after some investigation i could reduce it to the following problem: return objects of functions are handled as temporary objects, hence...
3
by: Mario | last post by:
Hello, I couldn't find a solution to the following problem (tried google and dejanews), maybe I'm using the wrong keywords? Is there a way to open a file (a linux fifo pipe actually) in...
25
by: Yves Glodt | last post by:
Hello, if I do this: for row in sqlsth: ________pkcolumns.append(row.strip()) ________etc without a prior:
32
by: Adrian Herscu | last post by:
Hi all, In which circumstances it is appropriate to declare methods as non-virtual? Thanx, Adrian.
8
by: Bern McCarty | last post by:
Is it at all possible to leverage mixed-mode assemblies from AppDomains other than the default AppDomain? Is there any means at all of doing this? Mixed-mode is incredibly convenient, but if I...
14
by: Patrick Kowalzick | last post by:
Dear all, I have an existing piece of code with a struct with some PODs. struct A { int x; int y; };
2
by: Ian825 | last post by:
I need help writing a function for a program that is based upon the various operations of a matrix and I keep getting a "non-aggregate type" error. My guess is that I need to dereference my...
0
by: amitvps | last post by:
Secure Socket Layer is very important and useful for any web application but it brings some problems too with itself. Handling navigation between secure and non-secure pages is one of the cumbersome...
399
by: =?UTF-8?B?Ik1hcnRpbiB2LiBMw7Z3aXMi?= | last post by:
PEP 1 specifies that PEP authors need to collect feedback from the community. As the author of PEP 3131, I'd like to encourage comments to the PEP included below, either here (comp.lang.python), or...
12
by: puzzlecracker | last post by:
is it even possible or/and there is a better alternative to accept input in a nonblocking manner?
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.