arya Patkar.

Rno. 41
fanel B (B2)

DSL Assiqnment 06.

faoblem Statement: Implement bingxy tree o perfopon
Eotlowing speratíong: Ireation ot
tecurfire
binaxy free &travetal

Objectire i Underatanding data stnucture

Io undentddalgoríthm devellpment.
Io stud trarnal technique
4: lo study ditfertat opfrations on
aearh
Binarg
rheory
DPinary is a data stutur
Tree Bavic : Binary Ireetup0
where eachnode has ahmost children
ferred to as left or ight child 1+ I+ is widdy
widcy
uscd in searchingsatín (a hiemrchial data
Hpreseotations.
tree
AloEuL 8inaxy treei A Binary" in which ereylerel
has 0 0r 2 chil
Camplete Binay Tree i A binary tre in whieh
the flly tled
5KeNd 'Bingry
Binay The: £y node hau oaly ene child.
Binany Search Irte: Al elements in the left subtre
qrc les than 0ot whilein aighb
Subtree qe more.
3
Ctating a
ot node
blnary trt typically inuale
inwalvn detininga
aSundann)
adhn constuctinthe.
FOR EDUCATIONL USE
trae ht inkin.Ades.
4THe ItavenaJ is the rotes ot vitting all the nodee
cf a ttt in &paifie or der. thert art thrte main tye
Gin -ordesVititing the i2# nade tirst then diralaqing
I then qting ta the right
A frt tdtr. Htrt. tirtt ditglay it then vitibing left
then right
lort brder 4trE. firtk lett then riqht e then displat
DCEturivt transal isit a natural way. whtrr the fundhan
rall itzcf for tVry subtrtt.
Non rtcuuik fravt al quíre uint stark to
stimlate the unttioD (al stack uud in eursian

ZMELtMENrATIDN
flatioum 69-kit open taarle linu Or its derivation.

1eat cb nditisns
D fve4 nodtu tithtr 0ar 2 children.
AI nMnal nodu hare 2childatn all leaxtt av.

The tre ha a Ianelam stmturt with a min t

.edu haxit q ant ar tuc childrn.

klqesitti utate.r(stsud traodu "raot)í

 che "y" fAatatt a memary tor Curr atgt data.
Set lttt 4 Tight of (arr nodeta NLk,
t m p l f t LuIr.
CtattI CLur ).
3
hyALacats a mtmary far CI à 4ctpt data,
stt laft and sighh t cuIr node ta N

ttmpl ULL
Anrdrrttmp lettl.
hint tem data,
itArderlih gh).
2.

cander

fkcardeI (tem
ErtAdertem tant.
 Post order
Alatrithm fattorderr(ttenode tenp) £
f (t rmpl NULL)
fost0rder (tenp left),
fort ordeI_Y (Htmp>igh):
funt (ttm >d ata);

)(opu
+rcenode *copy[TrceNtde *rost)

Allo cate memort tar tmp

ttmp> data root data
= (0py lroot lett);

returnttmpi

4MirOT root) E
Alaozithm ToiTOT-T (Treenode
Swap lett and right

OkEDUCATIONALL USE
 DI
Time (omplexity
Create = 0 (n)
Display 3 0(n)
)Delete
Copy
(oncusion: Thu, implemented Binany Tree ke rfom
O4eration on Binay tre
EAQs
A data structurc wwhere each_ node has at mort twe
childaco catled leßk a riqht child
DA roeey st uiuiting_alt mads in ate in a spei~L order.
T is imparting for cearchinmoditying T diplaying
tree data

areorder: Vitit oot, left subtrtt, Tighh subtree

rortozder: Viit Lett sußtrre,migbt subtreemot
Tnorder; Vuit lett ubtrte, 0ot, lhk ubtree.
Lel rdez: Viitnadee lered by leel.
4Rrurtiyt
4)Reurnin : Use function callr to troarerte the data.
Non-Reusriv tser data struuturet like stacke
4eues fo sfimdate the travcal withaut
reurion.

ram) FOR EDUCATIONAL USE

CODE:

RECURSIVE:
#include <stdio.h>

#include <stdlib.h>

struct treenode {
int data;
struct treenode *left;
struct treenode *right;
};
#define STACK_SIZE 100
struct treenode *stack[STACK_SIZE];
int top = -1;

void create_r(struct treenode *root) {

char a, b;
struct treenode *temp = root;

printf("Do you want to add it to the left side of %d (y/n)? \n", temp-
>data);
scanf(" %c", &a);

if (a == 'y') {
struct treenode *curr = (struct treenode *)malloc(sizeof(struct
treenode));
printf("Enter the data to the left of %d:\n", temp->data);
scanf("%d", &curr->data);
curr->left = NULL;
curr->right = NULL;
temp->left = curr;
create_r(curr);
}
 printf("Do you want to add it to the right side of %d (y/n)? \n", temp-
>data);
scanf(" %c", &b);

if (b == 'y') {
struct treenode *curr = (struct treenode *)malloc(sizeof(struct
treenode));
printf("Enter the data to the right of %d:\n", temp->data);
scanf("%d", &curr->data);
curr->left = NULL;
curr->right = NULL;
temp->right = curr;
create_r(curr);
}
}

void inorder_r(struct treenode *temp) {

if (temp != NULL) {
inorder_r(temp->left);
printf("%d \t", temp->data);
inorder_r(temp->right);
}
}

void preorder_r(struct treenode *temp) {

if (temp != NULL) {
printf("%d \t", temp->data);
preorder_r(temp->left);
preorder_r(temp->right);
}
}

void postorder_r(struct treenode *temp) {

if (temp != NULL) {
postorder_r(temp->left);
postorder_r(temp->right);
printf("%d \t", temp->data);
}
}

int main() {
int s;
struct treenode *root;
root = (struct treenode *)malloc(sizeof(struct treenode));

printf("Enter the data for the root:\n");

scanf("%d", &root->data);
 root->left = NULL;
root->right = NULL;
do {
printf("\n\n1. Create\n");
printf("2. Display Inorder\n");
printf("3. Display Preorder\n");
printf("4. Display Postorder\n");

scanf("%d",&s);
switch (s) {
case 1: create_r(root);
break;
case 2: printf("Inorder Traversal:\n");
inorder_r(root);
break;

case 3 :printf("\nPreorder Traversal:\n");

preorder_r(root);
break;

case 4: printf("\nPostorder Traversal:\n");

postorder_r(root);
break;
default : printf("Enter the valid input");
break;

}
while (s!=5);
return 0;
}
OUTPUT:

Enter the data for the root:

1. Create

2. Display Inorder

3. Display Preorder

4. Display Postorder
1

Do you want to add it to the left side of 1 (y/n)?

Enter the data to the left of 1:

Do you want to add it to the left side of 1 (y/n)?

Enter the data to the left of 1:

Do you want to add it to the left side of 2 (y/n)?

Do you want to add it to the right side of 2 (y/n)?

Enter the data to the right of 2:

Do you want to add it to the left side of 3 (y/n)?

Do you want to add it to the right side of 3 (y/n)?

Do you want to add it to the right side of 1 (y/n)?

Enter the data to the right of 1:

Do you want to add it to the left side of 4 (y/n)?

Enter the data to the left of 4:

Do you want to add it to the left side of 6 (y/n)?

Do you want to add it to the right side of 6 (y/n)?

n
Do you want to add it to the right side of 4 (y/n)?

Do you want to add it to the right side of 1 (y/n)?

1. Create

2. Display Inorder

3. Display Preorder

4. Display Postorder

Inorder Traversal:

2 3 1 6 4 1

1. Create

2. Display Inorder

3. Display Preorder

4. Display Postorder

Preorder Traversal:

1 1 2 3 4 6

1. Create

2. Display Inorder

3. Display Preorder

4. Display Postorder

Postorder Traversal:

3 2 6 4 1 1
NON RECURSIVE:

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

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

int top = -1;

int size = 10;

struct node *stack[10];

int isEmpty()
{
if (top == -1)
{
return 1;
}
else
return 0;
}

int isfull()
{
if (top == size - 1)
{
return 1;
}
else
return 0;
}

void push(struct node *ch)

{
if (!isfull())
{
top = top + 1;
stack[top] = ch;
}
}
struct node *pop()
{
if (!isEmpty())
{
struct node *temp = stack[top];
top = top - 1;
return (temp);
}
}

void create_nr(struct node *root)

{
int flag = 0;
char choice = 'y';
struct node *temp;

do
{
temp = root;
flag = 0;
struct node *curr;
curr = (struct node *)malloc(sizeof(struct node));
curr->left = NULL;
curr->right = NULL;
printf("Enter data:\n");
scanf("%d", &curr->data);

while (flag == 0)
{
int ch;
printf("Do you want to add a node to what position of %d?\n1.
Left\n2. Right\n", temp->data);
scanf("%d", &ch);

if (ch == 1)
{
if (temp->left == NULL)
{
temp->left = curr;
flag = 1;
}
temp = temp->left;
}
else if (ch == 2)
{
if (temp->right == NULL)
{
temp->right = curr;
 flag = 1;
}
temp = temp->right;
}
else
{
printf("Invalid choice!\n");
}
}

printf("Do you want to continue adding nodes? (y/n)\n");

scanf(" %c", &choice);
} while (choice == 'y');
}

void inorder_nr(struct node *root)

{
struct node *temp;
temp = root;

while (1)
{
while (temp != NULL)
{
push(temp);
temp = temp->left;
}
if (isEmpty())
{
break;
}
temp = pop();
printf("%d \t", temp->data);
temp = temp->right;
}
}

void preorder_nr(struct node *root)

{
struct node *temp;
temp = root;
while (1)
{
while (temp != NULL)
{
printf("%d \t", temp->data);
push(temp);
temp = temp->left;
 }
if (isEmpty())
{
break;
}
temp = pop();
temp = temp->right;
}
}

void postorder_nr(struct node *root)

{
struct node *temp;
temp = root;
while (1)
{
while (temp != NULL)
{
push(temp);
temp = temp->left;
}
if (stack[top]->right == NULL)
{
temp = pop();
printf("%d \t", temp->data);
}
while (!isEmpty() && stack[top]->right == temp)
{
temp = pop();
printf("%d \t", temp->data);
}
if (isEmpty())
{
break;
}
temp = stack[top]->right;
}
}
int main()
{
int s;
struct node *root;
root = (struct node *)malloc(sizeof(struct node));

printf("Enter the data for the root:\n");

scanf("%d", &root->data);

root->left = NULL;
 root->right = NULL;

do
{
printf("\n\n1. Create\n");
printf("2. Display Inorder\n");
printf("3. Display Preorder\n");
printf("4. Display Postorder\n");

scanf("%d", &s);
switch (s)
{
case 1:
create_nr(root);
break;
case 2:
printf("Inorder Traversal:\n");
inorder_nr(root);
break;

case 3:
printf("\nPreorder Traversal:\n");
preorder_nr(root);
break;

case 4:
printf("\nPostorder Traversal:\n");
postorder_nr(root);
break;
default:
printf("Enter the valid input");
break;
}

} while (s != 5);

return 0;
}

OUTPUT:

Enter the data for the root:

1. Create
2. Display Inorder

3. Display Preorder

4. Display Postorder

Enter data:

Do you want to add a node to what position of 1?

1. Left

2. Right

Do you want to continue adding nodes? (y/n)

Enter data:

Do you want to add a node to what position of 1?

1. Left

2. Right

Do you want to add a node to what position of 2?

1. Left

2. Right

Do you want to continue adding nodes? (y/n)

Enter data:

Do you want to add a node to what position of 1?

1. Left

2. Right

2
Do you want to continue adding nodes? (y/n)

Enter data:

Do you want to add a node to what position of 1?

1. Left

2. Right

Do you want to add a node to what position of 2?

1. Left

2. Right

Do you want to add a node to what position of 2?

1. Left

2. Right

Do you want to continue adding nodes? (y/n)

1. Create

2. Display Inorder

3. Display Preorder

4. Display Postorder

Inorder Traversal:

5 2 2 1 4

1. Create

2. Display Inorder

3. Display Preorder
4. Display Postorder

Preorder Traversal:

1 2 2 5 4

1. Create

2. Display Inorder

3. Display Preorder

4. Display Postorder

Postorder Traversal:

5 2 2 4 1