Counting nodes in a binary tree with odd values, using an iterative algorithm

Question

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

Basically my idea is to use the general scheme of iterative binary tree visit to do that:

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

Now I know that this one should be in Pre-order block:

      if T->key % 2 = 1 then
          ret = T->key

The rsx = assignment should be in-order, and rdx = assignment and last block should be in post-order. Now here I'm stuck, I ask if someone could help me to understand how finish the algorithm.

This is my first attempt that should work:

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

This solutions works if I assume that a pop on an empty stack returns 0. Any other suggestions? Improvements? Is it really correct? Please can I have some feedback? Many thanks

Working code (main.c):

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "stack_int.h"
#include "tree.h"

int countOddRic(tree_p T){
    int ret = 0;
    if(T != NULL){
        if(T->key % 2 == 1){
            ret = T->key;
        }

        int rsx = countOddRic(T->left);
        int rdx = countOddRic(T->right);

        ret = ret + rsx + rdx;
    }
    return ret;
}

int countOddIte(tree_p T){
tree_p curr = T;
tree_p next = NULL;
tree_p last = NULL;

stack *S = init_stack(100);
stack_int *Sret = init_stackInt(100);
stack_int *Srsx = init_stackInt(100);

int ret = 0;

while(curr != NULL || !isEmptyStack(S)){
    ret = 0;

    if(curr != NULL){
        //printf("pre-order: %d\n", curr->key);

        if(curr->key % 2 == 1){
            ret = curr->key;
        }
        Sret = pushInt(Sret, ret);

        S = push(S, curr);
        next = curr->left;
    }else{
        curr = top(S);

        if(last != curr->right){
            //printf("in-order: %d\n", curr->key);
            Srsx = pushInt(Srsx, popInt(Sret));
        }

        if(last != curr->right && curr->right != NULL){
            next = curr->right;
        }else{
            //printf("post-order: %d\n", curr->key);
            int rdx = popInt(Sret);
            int rsx = popInt(Srsx);
            int r = popInt(Sret);

            ret = rdx + rsx + r;

            Sret = pushInt(Sret, ret);

            pop(S);
            next = NULL;
        }

    }

    last = curr;
    curr = next;
}

printf("\nRet = %d\n", ret);
}


int main(void){

tree_p T = NULL;
insert(&T, 54);
insert(&T, 12);
insert(&T, 46);
insert(&T, 78);
insert(&T, 6);
insert(&T, 434);
insert(&T, 44);
insert(&T, 4);
insert(&T, 552);
insert(&T, 216);
insert(&T, 47);
insert(&T, 892);
insert(&T, 74);
insert(&T, 62);
insert(&T, 414);
insert(&T, 4442);
insert(&T, 86);
insert(&T, 4618);
insert(&T, 798);
insert(&T, 74);
insert(&T, 554);
insert(&T, 45);
insert(&T, 776);
insert(&T, 98);
insert(&T, 36);
insert(&T, 211);
insert(&T, 24);

printf("Count: %d\n", countOddRic(T));

countOddIte(T);
return 0;
}

stack.c:

#include "stack.h"


stack *init_stack(int size) {
stack *S = (stack*) malloc(sizeof(stack));
if (S == NULL) {
    exit(-1);
}

S->size = size;
S->array = (tree_p*) malloc(size * sizeof(tree_p));
if (S->array == NULL) {
    exit(-1);
}
S->last = 0;

return S;

}


int isEmptyStack(stack *S) {
return S->last == 0;

}


int isFullStack(stack *S) {

return S->last == S->size - 1;

}


stack *push(stack *S, tree_p elem) {
if (isFullStack(S))
    return S;

S->last++;
S->array[S->last] = elem;

return S;

}


tree_p pop(stack *S) {
if (isEmptyStack(S))
    return ERR_EMPTY_STACK;
S->last--;
return S->array[S->last + 1];

}


tree_p top(stack *S) {
if (isEmptyStack(S))
    return ERR_EMPTY_STACK;
return S->array[S->last];

}


void freeStack(stack *S){
if(S != NULL){
    free(S->array);
    S->array = NULL;
    free(S);
}

}


void printStack(stack *S) {
if (isEmptyStack(S))
    return;

tree_p e = pop(S);
printf("|%d", e->key);
printStack(S);
push(S, e);
}

stack.h:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "tree.h"

#ifndef STACK_H_
#define STACK_H_

#define ERR_EMPTY_STACK NULL

typedef struct {
    int size;
    int last;
    tree_p *array;
} stack;

stack *init_stack(int size);
void fillRandomStack(stack *S, int nElem);

int isEmptyStack(stack *S);
int isFullStack(stack *S);

stack *push(stack *S, tree_p elem);
tree_p pop(stack *S);
tree_p top(stack *S);

void freeStack(stack *S);

void printStack(stack *S);

#endif

stack_int.c:

#include "stack_int.h"

stack_int *init_stackInt(int size) {
    stack_int *S = (stack_int*) malloc(sizeof(stack_int));
    if (S == NULL) {
        exit(-1);
    }

    S->size = size;
    S->array = (int*) calloc(size + 1, sizeof(int));
    if (S->array == NULL) {
        exit(-1);
    }

    return S;
}    

void fillRandomStackInt(stack_int *S, int nElem){
    while(!isFullStackInt(S) && nElem > 0){
        pushInt(S, rand() % 500);
        nElem--;
    }
}    

int isEmptyStackInt(stack_int *S) {
    return S->array[0] == 0;
}    

int isFullStackInt(stack_int *S) {
    return S->array[0] == S->size - 1;
}

stack_int *pushInt(stack_int *S, int elem) {
    if (isFullStackInt(S))
        return S;

    S->array[0]++;
    S->array[S->array[0]] = elem;

    return S;
}

int popInt(stack_int *S) {
    if (isEmptyStackInt(S))
        return ERR_EMPTY_STACK_INT;
    S->array[0]--;
    return S->array[S->array[0] + 1];
}

int topInt(stack_int *S) {
    if (isEmptyStackInt(S))
        return ERR_EMPTY_STACK_INT;
    return S->array[S->array[0]];
}

void freeStackInt(stack_int *S){
    if(S != NULL){
        free(S->array);
        S->array = NULL;
        free(S);
    }
}

stack_int.h:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#ifndef STACK_INT_H_
#define STACK_INT_H_

#define ERR_EMPTY_STACK_INT 0

typedef struct {
    int size;
    int *array;
} stack_int;

stack_int *init_stackInt(int size);
void fillRandomStackInt(stack_int *S, int nElem);

int isEmptyStackInt(stack_int *S);
int isFullStackInt(stack_int *S);

stack_int *pushInt(stack_int *S, int elem);
int popInt(stack_int *S);
int topInt(stack_int *S);

void freeStackInt(stack_int *S);

void printStackInt(stack_int *S);

#endif

tree.c:

#include "tree.h"


void insert(tree_p *tree, int val) {
tree_p temp = NULL;
if(!(*tree)) {
    temp = (tree_p) malloc(sizeof(tree));
    temp->left = temp->right = NULL;
    temp->key = val;
    *tree = temp;
    return;
}

if(val < (*tree)->key) 
    insert(&(*tree)->left,val);
else if(val > (*tree)->key)
    insert(&(*tree)->right,val);
else
    return;

}

tree.h

#include <stdlib.h>
#include <stdio.h>

#ifndef TREE_H_
#define TREE_H_

typedef struct tree {
    int key;
    struct tree *left;
    struct tree *right;
} tree, *tree_p;

void insert(tree_p *tree, int val);
#endif

Answer 1

Overthinking it

I think when you translated the code from recursive to iterative, you were overthinking the order of operations (i.e. preorder vs inorder vs postorder). For this task, you are simply summing all the key values that are odd. So it actually doesn't matter which traversal order you use. You can just use whatever order is the most convenient.

In your iterative solution, you created three stacks. The purpose of the integer stacks was (I believe) so that you could simulate the correct order of the additions. But as mentioned above, additions can be made in any order, as long as you add each odd key exactly once to the return value. So the integer stacks are totally unnecessary.

Other things

• Your indentation is off everywhere, but I'm guessing you pasted the code incorrectly.
• You never free your stacks, so you have a memory leak there.
• Your header files include headers that aren't needed by the header files themselves. You should move those #includes into the .c files, where they are actually needed.

Simplified solution

Here is how you could have written your function, without any of the integer stacks:

int countOddIte(tree_p root)
{
    stack *S   = init_stack(100);
    int    ret = 0;

    push(S, root);

    while (!isEmptyStack(S)) {
        tree_p curr = pop(S);

        if (curr == NULL)
            continue;
        if (curr->key % 2 == 1)
            ret += curr->key;
        push(S, curr->left);
        push(S, curr->right);
    }
    freeStack(S);

    printf("\nRet = %d\n", ret);
}

Simulating exact recursion

According to a comment by the OP, the goal was to simulate the recursion exactly no matter how strange/inefficient the code turned out. So here, I will present a rewrite to accomplish that goal (although the code is quite ugly). A few items to note:

• I only used one stack, but each stack frame contains the exact information that would be contained in a normal recursive stack frame for a function.
• I maintain a return address at all times, which determines where in the caller the function should return to. This simulates what really happens when a function returns to its caller. I had to use goto statements to accomplish this.
• I used a macro on the recursive call site to simplify what the call looked like (since there were two calls almost exactly the same).
• I combined all your code into one .c file:

Here is the code:

#include <stdio.h>
#include <stdlib.h>

typedef struct tree {
    int key;
    struct tree *left;
    struct tree *right;
} tree, *tree_p;

void insert(tree_p *tree, int val)
{
    tree_p temp = NULL;
    if(!(*tree)) {
        temp = (tree_p) malloc(sizeof(tree));
        temp->left = temp->right = NULL;
        temp->key = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->key)
        insert(&(*tree)->left,val);
    else if(val > (*tree)->key)
        insert(&(*tree)->right,val);
    else
        return;
}

int countOddRecursive(tree_p T)
{
    int ret = 0;
    if(T != NULL){
        if(T->key % 2 == 1){
            ret = T->key;
        }

        ret += countOddRecursive(T->left);
        ret += countOddRecursive(T->right);
    }
    return ret;
}

typedef struct stackNode {
    tree_p T;
    int ret;
    int returnAddr;
} stackNode;

// This macro simulates a recursive function call by pushing the current
// frame onto the stack and setting the variables up as if the function
// had just been called.
#define countOddSimRecurse(newT, newReturnAddr)     \
    stack[stackIndex].T            = T;             \
    stack[stackIndex].ret          = ret;           \
    stack[stackIndex++].returnAddr = returnAddr;    \
    T                              = newT;          \
    returnAddr                     = newReturnAddr; \
    goto begin;

int countOddIterative(tree_p T)
{
    stackNode stack[100];
    int       stackIndex = 0;
    int       ret        = 0;
    int       funcRet    = 0;
    int       returnAddr = 0;

begin:
    ret = 0;
    if (T != NULL) {
        if(T->key % 2 == 1){
            ret = T->key;
        }
        countOddSimRecurse(T->left, 1);
ret1:
        ret += funcRet;
        countOddSimRecurse(T->right, 2);
ret2:
        ret += funcRet;
    }

    // If the stackIndex is 0, we are returning from the initial
    // function call, so return for real.
    if (stackIndex == 0)
        return ret;

    // Otherwise we are simulating a return to one of the two possible
    // return addresses, ret1 or ret2.  We pop the previous frame from the
    // stack and return to wherever returnAddr tells us to return to.
    // Note that the value of "ret" is copied to "funcRet" because when
    // we return from this recursive call, "ret" will be set to the value
    // that the caller had for that variable.
    int returnTo = returnAddr;
    funcRet    = ret;
    T          = stack[--stackIndex].T;
    ret        = stack[  stackIndex].ret;
    returnAddr = stack[  stackIndex].returnAddr;

    if (returnTo == 1)
        goto ret1;
    else if (returnTo == 2)
        goto ret2;
}

int main(void)
{
    tree_p T = NULL;
    insert(&T, 54);
    insert(&T, 12);
    insert(&T, 46);
    insert(&T, 78);
    insert(&T, 6);
    insert(&T, 434);
    insert(&T, 44);
    insert(&T, 4);
    insert(&T, 552);
    insert(&T, 216);
    insert(&T, 47);
    insert(&T, 892);
    insert(&T, 74);
    insert(&T, 62);
    insert(&T, 414);
    insert(&T, 4442);
    insert(&T, 86);
    insert(&T, 4618);
    insert(&T, 798);
    insert(&T, 74);
    insert(&T, 554);
    insert(&T, 45);
    insert(&T, 776);
    insert(&T, 98);
    insert(&T, 36);
    insert(&T, 211);
    insert(&T, 24);

    printf("Count (recursive): %d\n", countOddRecursive(T));
    printf("Count (iterative): %d\n", countOddIterative(T));
    return 0;
}