CODEWITHSUNDEEP
crecursiontree
kikikey
kikikey

Reputation: 105

How do I modify my tree traversal program that I wrote in C so that it doesn't rely on recursion?

I have a program written in C that traverses a tree in reverse pre-order, reverse in-order, and reverse post-order whose individual functions rely heavily on recursion. How would I go about modifying these functions so that they perform the exact same task but without using any sort of recursion? I've spent many hours trying to figure that out by using variables that temporarily store values but I keep drawing a blank unfortunately. I'm using the GCC compiler on Ubuntu Linux BTW.

Here is my code:

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


struct node 
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 


struct node* newNode(int data) 
{ 
    struct node* node = (struct node*) 
                                malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 

    return(node); 
} 


void reversePostOrder(struct node* node) 
{ 
    if (node == NULL) 
        return; 


    reversePostOrder(node->right);


    reversePostOrder(node->left); 



    printf("%d ", node->data); 
} 


void reverseInOrder(struct node* node) 
{ 
    if (node == NULL) 
        return;  


    reverseInOrder(node->right);


    printf("%d ", node->data); 


    reverseInOrder(node->left);


} 


void reversePreOrder(struct node* node) 
{ 
    if (node == NULL) 
        return; 


    printf("%d ", node->data); 


    reversePreOrder(node->right);


    reversePreOrder(node->left); 


}    


int main() 
{ 


    struct node *root = newNode(1);
    root->left           = newNode(-2);
    root->right      = newNode(-3);
    root->left->left     = newNode(4);
    root->left->right = newNode(5);
    root->right->left =newNode(6);
    root->right->right=newNode(7);
    root->left->right->left=newNode(-8);
    root->left->right->right=newNode(-9);
    root->right->right->left=newNode(10);
    root->right->right->right=newNode(11);
    root->right->right->right->left=newNode(-12);
    root->right->right->right->right=newNode(-13);
    root->right->right->right->right->left=newNode(14);
    printf("\nReverse Preorder traversal of binary tree is \n"); 
    reversePreOrder(root); 

    printf("\nReverse Inorder traversal of binary tree is \n"); 
    reverseInOrder(root); 

    printf("\nReverse Postorder traversal of binary tree is \n"); 
    reversePostOrder(root); 

    getchar(); 
    return 0; 
}

Upvotes: 2

Views: 82

Answers (2)

Reshad
Reshad

Reputation: 239

you can use a stack to store the parent and an array if a node was previously processed or not before. example for inorder

push(root)
while stack is not empty()
   parent=stack.top()
   if parent->left and done[parent->left]==false
       left=parent->left
       push(parent)
       done[left]=true
       continue
   if done[parent]==false
       process(parent)
       done[parent]=true
   if parent->right and done[parent->right]==false
       right=parent->right
       push(right)
       done[right]=true
       continue
   stack.pop()

Upvotes: 0

Kaz
Kaz

Reputation: 58510

The problem is made difficult because your list nodes do not have pointers to their parents. When an iterative/imperative procedure marches down the left or right link of the current node to navigate to another node, it has no reverse path.

There are two general approaches to the problem:

  1. Maintain an explicit stack which enables the procedure to navigate to the parent.

  2. Mutate the tree itself temporarily to provide a return path. That is to say, overwrite the left and right links with reverse pointers to the parent temporarily; then restore the values when returning up the tree.

If the tree is a balanced tree with a guaranteed maximum depth, then (1) can be implemented with a reasonably small, fixed-size array.

Upvotes: 1

Related Questions