Re: counting BST nodes using iteration

"subramanian100in@xxxxxxxxx, India" wrote:
On Mar 24, 9:14 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
"subramanian10...@xxxxxxxxx, India" wrote:

... snip ...

I have written the following function to count the nodes in a BST
without using recursion. It uses iteration.

You don't need all that. A simple recursive implementation follows:

size_t nodecount(node *root) {

if (!root) return 0;
else return 1 + nodecount(root->left) + nodecount(root->right);

} /* untested */

which you can easily (and mechanically) convert to iteration with a
local stack, if desired.

The problem is how to declare the stack size because we do not know
the number of nodes in advance. Kindly explain me the logic of
converting the above recursion into iteration. I am unable to
convert it into stack version without using realloc.

Just create a stack mechanism. You can worry about its details
later. For now, just make it big enough. You can do the
implementation with four macros:

PUSH(item)
POP
STACKNOTEMPTY
STACKNOTFULL

the last two returning booleans, POP returning an item, and PUSH
returning nothing. In future didding the macros lets you
experiment.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: Is this tai-recursion?
    ... There is no difference between tail-recursion and iteration. ... That's why tail-recursion is so simple, ... fetch next instruction from instruction pointer ... instructions will manipulate the processor stack. ...
    (comp.lang.scheme)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: iterative copying of binary expression trees
    ... tail recursion as de facto optimized (bounded stack space). ... "Functional iteration" makes high sense IMHO. ... and an iterative procedure from an iterative process. ...
    (comp.lang.lisp)
  • Re: counting BST nodes using iteration
    ... without using recursion. ... It uses iteration. ... delete stack. ... If you have a decent stack ADT, ...
    (comp.programming)
  • Re: counting BST nodes using iteration
    ... It uses iteration. ... size_t nodecount(node *root) { ... The problem is how to declare the stack size because we do not know ... Kindly explain me the logic of converting the above recursion into ...
    (comp.programming)
Loading