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

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


### 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;
} 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
stack[stackIndex].T            = T;             \
stack[stackIndex].ret          = ret;           \
T                              = newT;          \
goto begin;

int countOddIterative(tree_p T)
{
stackNode stack[100];
int       stackIndex = 0;
int       ret        = 0;
int       funcRet    = 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
// 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.
funcRet    = ret;
T          = stack[--stackIndex].T;
ret        = stack[  stackIndex].ret;

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;
}

• Hi, thanks for answer but I've not overthinking it. My purpose is to exactly simulate recursion with activation record, I doesn't really care about what the code does. I'm looking for a better scheme,if any, for an exact simulation of recursion Jun 24, 2017 at 8:54