#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Exactly simulate recursive algorithm into Iterative

Member Posts: 1

Hello to everyone, I've this problem that I'm not able to solve for days, and I'm almost loosing my mind on it.
Well I've to simulate exactly a recursive algorithm with an iterative one. Assuming that I have a binary search tree that contains only a key and two references at his right and left child I want to do this count:

``````CountOddRec(T)
ret = 0
if T != NIL then
if T->key % 2 = 1 then
ret = T->key
rsx = CountOddRec(T->sx);
rdx = CountOddRec(T->dx);
ret = ret + rsx + rdx;
return ret
``````

It's very basic, just for learing purpose. My idea is to use this algorithm for a general binary tree visit:

``````VisitIter(T)
last = NIL
curr = T
stk = NULL
while (curr != NIL || stk != NIL) do
if curr != NIL then
//Pre-order visit
stk = push(stk, curr)
next = curr->sx
else
curr = Top(stk)

if (last != curr-> dx) then
//In-order visit

if (last != curr-> dx  && curr->dx != NULL) then
next  = curr->dx
else
//Post-order visit
stk = pop(stk)
next = NIL
last = curr
curr = next
``````

And so this is the solution I've reached:

``````CountOddIter(T)
last = NIL
curr = T

stk = NULL //stack
Sret = NULL //stack
Srsx = NULL //stack

ret = 0

while (curr != NIL || stk != NIL) do
ret = 0
if curr != NIL then
//Pre-order block
if (curr->key % 2 == 1) then
ret = curr->key

Sret = push(Sret, ret)

stk = push(stk, curr)
next = curr->sx
else
curr = Top(stk)

if (last != curr-> dx) then
//In-order block
Srsx = push(Srsx, pop(Sret))

if (last != curr-> dx  && curr->dx != NULL) then
next  = curr->dx
else
//Post-order block
rdx = pop(Sret)
rsx = pop(Srsx)
r = pop(Sret)

ret = rdx + rsx + r

Sret = push(Sret, ret)

stk = pop(stk)
next = NIL
last = curr
curr = next
``````

Now I've tested both visit and solution and as I can see they works. But I'm pretty unsure about its effective correction, moreover I would like to learn if there is a method to improve solution (if correct).
I hope that here someone could help me to understand this, maybe too much easy, problem.
Many thanks!

Tagged: