Different types of Traversing without Recursion
Here we have already learned implementation of Inorder traversing without recursion click the button below to learn the implementation diffrent type of traversing without recursion.
We can perform Inorder Tree Traversal without Recursion in C in two ways, First we can use stack and other one is iterative method known as morris traversal. In given example we are using stack method to perform inorder traversal on tree. Inorder traversal of tree is Left->Root->Right. Here we will learn how to implement inorder traversal of tree using stack and its algorithm.
#include<stdio.h> #include<stdlib.h> struct node // node defining for tree { struct node* left; struct node* right; int data; }; struct stack // node defining for stack { struct node* data; struct stack* next; }; void push(struct stack** top,struct node* n); //function declation struct node* pop(struct stack** top); int isEmpty(struct stack* top); int tree_traversal(struct node* root) //Inorder Traversing function { struct node* temp = root; struct stack* s_temp = NULL; int flag = 1; while(flag) //Loop run untill temp is null and stack is empty { if(temp){ push(&s_temp,temp); temp = temp->left; } else{ if(!isEmpty(s_temp)){ temp = pop(&s_temp); printf("%d",temp->data); temp = temp->right; } else flag = 0; } } } void push(struct stack** top,struct node* n) //push node in stack { struct stack* new_n = (struct stack*)malloc(sizeof(struct stack)); new_n->data = n; new_n->next = (*top); (*top) = new_n; } int isEmpty(struct stack* top) // check if stack is empty { if(top==NULL) return 1; else return 0; } struct node* pop(struct stack** top_n) // pop the node from stack { struct node* item; struct stack* top; top = *top_n; item = top->data; *top_n = top->next; free(top); return item; } struct node* create_node(int data) // create a node for tree { struct node* new_n = (struct node*)malloc(sizeof(struct node)); new_n->data = data; new_n->left = NULL; new_n->right = NULL; return (new_n); } int main() { struct node* root; root = create_node(8); root->left = create_node(5); root->right = create_node(4); root->left->left = create_node(7); root->left->right = create_node(6); tree_traversal(root); return 0; }
output: 75684
Create_node():
Here we have already learned implementation of Inorder traversing without recursion click the button below to learn the implementation diffrent type of traversing without recursion.
Login/Signup to comment