BINARY TREE NON-RECURSIVE

TREE TRAVERSAL
Name: Om Lohade
Class: IT – C
PRN: 12320123
Roll no.: SEDA-3

C code for creating BT/BST and inserting element of user choice, Non-Recursive
Inorder, Preorder, Tree Traversal

Explanation:
The provided code implements Preorder and Inorder Traversals of a binary tree using
iterative methods with a custom stack data structure. In Preorder Traversal, the root node is
visited first, followed by the left subtree, and then the right subtree. In Inorder Traversal, the
left subtree is visited first, then the root node, and finally the right subtree. Both functions
utilize a temporary pointer and a stack to perform iterative node processing, avoiding
recursion. The traversal sequences are printed for the binary tree created using user-input
values, offering an efficient and space-saving approach to traverse the tree nodes.

#include<stdio.h>

#include<stdlib.h>

struct node

struct node *left;

struct node *right;

int data;
};

struct stack

struct node *data;

struct stack *next;

};

void push (struct stack **top, struct node *n)

struct stack *new_n = (struct stack *) malloc (sizeof (struct stack));

new_n->data = n;

new_n->next = (*top);

(*top) = new_n;

struct node *pop (struct stack **top_n)

struct node *item;

struct stack *top;

top = *top_n;

item = top->data;

*top_n = top->next;

free (top);

return item;

int isEmpty (struct stack *top) // check if stack is empty

{
 if (top == NULL)

return 1;

else

return 0;

int pre_traversal (struct node *root)

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)

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

push (&s_temp, temp);

temp = temp->left;

else

if (!isEmpty (s_temp))

temp = pop (&s_temp);

temp = temp->right;

else

flag = 0;
 }

int inorder_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;

struct node *create_node (int data)

struct node *new_n = (struct node *) malloc (sizeof (struct node));

new_n->left = NULL;

new_n->right = NULL;

return (new_n);

int main ()

struct node *root;

int a[5];

printf("Enter 5 integers: ");

for(int i=0; i<5;i++)

scanf("%d", &a[i]);

printf("\nYour tree looks like:\n\n %d \n %d %d \n %d %d", a[0],a[1],a[2],a[3],a[4]);

root = create_node (a[0]);

root->left = create_node (a[1]);

root->right = create_node (a[2]);

root->left->left = create_node (a[3]);

root->left->right = create_node (a[4]);

printf("\nPreorder form: ");

pre_traversal(root);

printf("\nInorder form: ");

inorder_traversal(root);

return 0;

}
C code for creating BT/BST and inserting element of user choice, Non-Recursive
Postorder Traversal

Explanation:
This code implements an iterative Postorder Traversal of a binary tree using a custom stack
data structure. It defines a binary tree node structure and a stack structure. The `postorder`
function traverses the tree in a postorder manner without recursion. It uses a stack to keep
track of nodes during traversal. The function iteratively processes the left child nodes,
pushes nodes with right children onto the stack, and then processes the right child nodes.
Finally, it prints the data of the current node in postorder sequence. The Postorder Traversal
result is printed for the binary tree constructed using user-input values.

#include<stdio.h>

#include<stdlib.h>

#define MAX_SIZE 100

struct Node

{
 int data;

struct Node *left, *right;

};

struct Stack

int size;

int top;

struct Node **array;

};

struct Node *newNode (int data)

struct Node *node = (struct Node *) malloc (sizeof (struct Node));

node->data = data;

node->left = node->right = NULL;

return node;

struct Stack *createStack (int size)

struct Stack *stack = (struct Stack *) malloc (sizeof (struct Stack));

stack->size = size;

stack->top = -1;

stack->array =

(struct Node **) malloc (stack->size * sizeof (struct Node *));

return stack;

int isFull (struct Stack *stack)

{
 return stack->top - 1 == stack->size;

int isEmpty (struct Stack *stack)

return stack->top == -1;

void push (struct Stack *stack, struct Node *node)

if (isFull (stack))

return;

stack->array[++stack->top] = node;

struct Node *pop (struct Stack *stack)

if (isEmpty (stack))

return NULL;

return stack->array[stack->top--];

struct Node *peek (struct Stack *stack)

if (isEmpty (stack))

return NULL;

return stack->array[stack->top];

void postorder (struct Node *root)

{
if (root == NULL)

return;

struct Stack *stack = createStack (MAX_SIZE);

do

while (root)

if (root->right)

push (stack, root->right);

push (stack, root);

root = root->left;

root = pop (stack);

if (root->right && peek (stack) == root->right)

pop (stack);

push (stack, root);

root = root->right;

else

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

root = NULL;

while (!isEmpty (stack));

int main ()

struct Node *root = NULL;

int a[7];

printf("Enter 7 integers:");

for(int i=0; i<7;i++)

scanf("%d", &a[i]);

printf("\nYour tree looks like:\n\n %d \n %d %d \n %d %d %d %d",

root = newNode (a[0]);

root->left = newNode (a[1]);

root->right = newNode (a[2]);

root->left->left = newNode (a[3]);

root->left->right = newNode (a[4]);

root->right->left = newNode (a[5]);

root->right->right = newNode (a[6]);

printf ("\nPost order traversal of binary tree is: ");

postorder(root);

return 0;