Rewrite recursive algorithm in iterative way

[nowy20180820]

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

struct Node
{
    int data;
    struct Node *prev;
    struct Node *next;
};

struct List
{
    struct Node *head;
    struct Node *tail;
};

void Init(struct List *L)
{
    L->head = NULL;
    L->tail = NULL;
}

int IsEmpty(struct List L)
{
    return L.head == NULL;
}

void InsertLast(struct List *L,int dd)
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node ));
    newNode->data = dd;
    newNode->next = NULL;
    if(L->tail == NULL)
        L->head = newNode;
    else
        L->tail->next = newNode;
    newNode->prev = L->tail;
    L->tail = newNode;
}

void DeleteFirst(struct List *L)
{
    struct Node *temp;
    if(L->head != NULL)
    {
        temp = L->head;
        if(L->head->next == NULL)
            L->tail = NULL;
        else
            L->head->next->prev = NULL;
        L->head = L->head->next;
        free(temp);
    }
}

void DisplayForward(struct List L)
{
    struct Node *current = L.head;
    int counter = 0;
    printf("List(first-->last): ");
    while(current != NULL)
    {
        printf("%d ",current->data);
        counter++;
        current = current->next;
    }
    printf("\n");
    printf("Number of nodes on the list : %d\n",counter);
}

void DisplayBackward(struct List L)
{
    struct Node *current = L.tail;
    int counter = 0;
    printf("List(last-->first): ");
    while(current != NULL)
    {
        printf("%d ",current->data);
        counter++;
        current = current->prev;
    }
    printf("\n");
    printf("Number of nodes on the list : %d\n",counter);
}

void BSTinsert(struct Node *x, struct Node **t)
{
    if((*t) == NULL)
       (*t) = x;
    else if((*t)->data == x->data)
        BSTinsert(x,&((*t)->prev));
    else if((*t)->data < x->data)
        BSTinsert(x,&((*t)->next));
    else 
        BSTinsert(x,&((*t)->prev));
}

void BSTtoDLL(struct Node *t,struct List *L)
{
    if(t != NULL)
    {
        BSTtoDLL(t->prev,L);
        if(L->head == NULL)
            L->head = t;
        else
            L->tail->next = t;
        t->prev = L->tail;
        L->tail = t;
        BSTtoDLL(t->next,L);
    }
}

void BSTSort(struct List *L)
{
    struct Node *temp;
    struct Node *T = NULL;
    while(L->head != NULL)
    {
        temp = L->head;
        if(L->head->next == NULL)
            L->tail = NULL;
        else
            L->head->next->prev = NULL;
        L->head = L->head->next;
        temp->prev = NULL;
        temp->next = NULL;
        BSTinsert(temp,&T);
    }
    BSTtoDLL(T,L);
}

int main(void) {
	// your code goes here
	struct List L;
	int k,n,m;
	Init(&L);
	srand(time(NULL));
	scanf("%d %d",&n,&m);
	for(k=0;k<n;k++)
	    InsertLast(&L,rand()%m);
	DisplayForward(L);
	DisplayBackward(L);
	BSTSort(&L);
	DisplayForward(L);
	DisplayBackward(L);
	while(!IsEmpty(L))
	    DeleteFirst(&L);
    system("PAUSE");  
	return 0;
}

I gave you full code to show that recursive functions work well

How can I replace recursion with iteration ?

void BSTinsert(struct Node *x, struct Node **t)

I saw non recursive version of this function
and i think it works quite well

void BSTtoDLL(struct Node *t,struct List *L)

I think i see in this function tail call
but there is other recursive call

How to replace recursion with iteration
without allocating memory for new nodes
and in time O(n)

[dhayden]

void BSTinsert(struct Node *x, struct Node **t)
{
    while (*t) {
        if((*t)->data == x->data)
            t = &(*t)->prev;
        else if((*t)->data < x->data)
            t = &(*t)->next;
        else
            t = &(*t)->prev;
    }
    (*t) = x;
}

or even better:

void BSTinsert(struct Node *x, struct Node **t)
{
    while (*t) {
        if((*t)->data >= x->data)  // changed == to >=
            t = &(*t)->prev;
        else if((*t)->data < x->data)
            t = &(*t)->next;
    }
    (*t) = x;
}

This looks like C code, not C++. If you're taking C++, have you learned about constructors? How about references? Both of these would make the code cleaner.

[nowy20180820]

I know that it is C like code
but i would like to know how to replace recursion with iteration
especially in function

void BSTtoDLL(struct Node *t,struct List *L)

I think i see in this function tail call

I gave C like code because if stack is needed for the other recursive call
i prefer to not use STL stack to be able to translate the code to other languages easily

[dhayden]

Perhaps I misunderstood. When you said:

How can I replace recursion with iteration ?
void BSTinsert(struct Node *x, struct Node **t)

I thought you meant you wanted a non-recursive version of BSTinsert.

As for a non-recursive version of BSTtoDLL(), if you google "binary tree iterative DFS" you'll find some pointers, but involve creating your own stack to store the intermediate data. To me, it's much easier to use the call stack to do that - i.e., to do it recursively.

[jonnin]

i prefer to not use STL stack to be able to translate the code to other languages easily

what language? Most major languages have either a stack object or some other container that can be used as a stack with minimal aggravation, so using c++ stl stack to get the algorithm is fine, just replace it with the other language's tool.

Are you using something that specifically has no good way to represent a stack and disallows recursion? I used to have to do this stuff on embedded systems that did not allow recursion; sometimes the expanded solution is rather involved. Every language I know can cook up a stack without much trouble, but often you don't want to waste the extra memory.

I would also offer: don't use a tree if you don't want recursion or annoying algorithms. You can do anything a tree can do in an array, or with something else. If you need dynamic growth to giant unknown sizes, using a primitive language, it could be tricky, but usually people need less features than they think they need...

[nowy20180820]

I found linked list class i translated from Lafore's example in Java
but it is too lengthy to paste here
I tried to look for non recursive inorder traversal of binary tree but i cant get correct result

[jonnin]

riddle me this... what does inorder traversal *produce* from a BST?

[nowy20180820]

... a sequence of nodes with sorted key values

I found recursive inorder traversal and non recursive BST insert
in CLRS introduction to algorithms
If we replace printing node data with inserting at tail of the list
we will get BSTtoDLL function

In CLRS introduction to algorithms iterative inorder traversal was given as homework
They wrote that exist two solutions
(easier with stack, and more difficult without stack)

[jonnin]

right.
so can you do it with a 'stack' (even if this is your own storage object or a vector or whatever)?

[nowy20180820]

I see tail call which can be replaced with the while loop
but there is another recursive call how can I replace it
with stl stack or my own stack

void BSTtoDLL(struct Node *t,struct List *L)
{
    while(t != NULL)
    {
        BSTtoDLL(t->prev,L);
        if(L->head == NULL)
            L->head = t;
        else
            L->tail->next = t;
        t->prev = L->tail;
        L->tail = t;
        t = t->next;
    }
}   

After replacing tail call with while loop
still there is recursive call