Howdy, Stranger!

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

Categories

Exactly simulate recursive algorithm into Iterative

Philip PuabhPhilip Puabh 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:
Sign In or Register to comment.