LENKED LIST DELETEAG NODES ( LINKED LIST DELETING NobéS h3

Nae in ngly Linked Lip+ beletng the Lat node 'n ingy Linked& Li's+
Deletinghe fivat

Algorthm
Algorithms
deleted is+ (START) Deleng (STAAT
Under
flow
StepL: Check fer underflew
Check for
StepL I f t r NuLL han
=
NULL, thun
Stat
If Prink Lik Li's is empky
Pi'w
uinkel Lst Empty Exit

Stepa fStart Next NULL hem

START Set Phr : Start

set PTRz
Stee 2 STAATNax
Se start= NULL
STAAT =
set
Step 8lement
delcted is phr>ifa Pit elemamt deluked is PTR >Info
Print
S+ep
StePS free CP). free (PTR
endf
Stoe PTA START
Step3 set

S+ep4 Repeat S+ep Somd 6 Until

A f t e r &eielion PTANext =NULL

PTR
20 Step s: s t LOC
Set PTR= PTR Next
S4ep6
 Sek Loc Next
NULL 48 LINKED LIST DELETENG NODES 49
Stee Specrfiecl Position
belehng the Nede from
Step free (eTA)
In &gly Liwkad ui
Star LoC
Algorithm
Delete LoCation (STAAT, LOC
After dehion Check fov Under flow
Step L
Sstarcd f PTA: NULL them
priwt Underflow

I emed poinkers
Tni'tialze the Counher
Step 2
Se+ T : O ;
Se p r Star

Repeat Step 4 to 6 untl I< LO

Step3:
Step4 Set+emp PTR

set PTR
= PTR Nex+
Steps
T+1
Sek I :
Step
Step7 Pri blemunt deldel is=PtY>ifo Tree Bada stuciure
So
P*r>Nox+0 T s e e . A Tree a non -liinear lata
set Temp- Neyt
=

Step 8
Structure in whu'ch items are
Step9:ree (P+r) aTomged in a Sorted sequemce.

T+ URed +o xepresent hierorchial

Sto TemP xelatonmp Exigst1'ng camongst
Seeral

Acnta items.
Root Levdl o

Afte e e t i o n
A
Levt

SHo Leuel 2

Levd 3
Tree TesminologyTree hos A e t
texminology Such as+

1 Root >I+ i» Special Begnal elata

ina tree. I+ 1s the firs+ i'n the
tem
of dlata item.
hierarchutal Aromgemak
+em.
In the Ai oot
above +xee,
item in a +ree
2 Node Each data
sCalled a nocle. In the qiuen
 Txee+here are 3 NoRle
Such as 7 Siblinga The Child nodes of a gien
A, 6,C, D, E, F, 7, H, T, J, K,
L,M Porennode are Called S.bling. Thy
are alho Called brothers.
T+ 8 the no. ofF
SDearee of a node In the en +able .

Subtree3 of a nodde in a uen tree are SiblingH of porent nod A.

B, C,D
The deqree of A = 3
H&T are Siblings of parent noole D
The degvee of C =1 enkive +ree shruxture i
of L = O 8Level>The hat +he
The legee Leve lled in Such a uoy
maxinmum clgree a level Q.
Degree of o ree7 the xoot node is aluways
+ree. In the given
of nases in a gisen
9Elge> It i
a Connecing Line ofP
+Tee the Nocle A mel node T heas moximum +hat s, +he Line drawn
+uwo nodes,
degree (3) so tht egree of tree ts 3 noe is
node +o another
from ome
S Terminal node A nooke with degree Calle& an &dge.
3ero 3 Calle erminal node. In a Seqmte of
loPath I H
ise +ree - E, J, C7, H, K,L Omd m are +he Source
Conselute edq, trom
+erminal nede deutinadiom node. Tn
ode +o +he
6 Nona-termina Node Any Noe who tree +he path
btween

Called non-termuinal the giuem

ecree ip not r o i A omd s.
node. 1n g n tree - A,B,C, D, EI are
, F) Cmd (E, T)
Non-+exmunal Node . A, B)
A 8 F>J
1Depth It is the maximum level o
noce in a Puen +see. In 4he 8TNARY TREES
Ony the
Yoot
+ree, +he noke A hauy tree is oa finite set of
en Sinary
maximum leuel. item which s Either mpty
data
se of Bjoint item Called
forest I t ias hg le
a
12 of Coista of a

+xees. In a qian +ree tf yoy

tuo disjoink brnary
TOOt d
Te move + yoot node +hen it belomes + h Left Subtree md
tree Called
the gion +ree, there is
o toreg. In oigh swbtree
+ree, Such cy.
foxes+ with ree
A. voot forest ib. mede Can hae
After remonng
In Binary +ree, Euery
are
Children which
moy 'mum of 2
Left Child
od Arght Chd
Known us

LeftSuetree ( ) roo
Toot

k Ri'yhk Sub+ree
 ypes of Binary
+sees>
TroueTsal of a &inary ee
ary 'n which each node
D full nary +reeA
ful
Euery I+ o way
's is ViBited Exactl nC(e
Tsee
T ree i'n +he +ree
a Chl manner.
node haus o or
n a Syptematic
We uge
There are three way8 whuth
tree Noe lestRigat
-

+o +rauerse a
L- Pre ovler
troueTBal NLR
tronserBal (LNR)
nary treeis 2 - I n oreler
tree A +xaversal CLAN)
Complete
hary
Tree 'f
all Levels
are
3 PoB+order
2 inary the L o
1Preorder Trauersal In ths
Complete
fille& Ex
Cept Possibly Lef+
Compl e te ly keys as
TaaeTsal method, he vootoke is
all
+he
L0t Leuel hag
Lesel omd Leuo
0 p o b l e .
e d t a: 2 vibited tirpt, +hen +h Le subtvee
Lesl a 24 Ownd finally thi riA Sobtree.
Leds a Algothm
TreeA Tre
i'ntukthal) Until a| nodes
ase trauerBed
-

3) Perfect nary
rodes heus tuwo
CAildren Cmcd
all iwhermal
a t +he Same Leusl Stept Visit xoot node.
Leaues are
chi'd +raverae Left Subtree.
in wch all Le wl heus
Stepa ReCurgiuely
Leo Le +rauerAR Right Sobhre
Step3: Aetursively
Led
Odo6ooady
 8 Sinary Seorch tree (8ST)
inery SeoTCh tree anode- buyeA birary
( +ree dota Struchure whch hag 4he folloiing Rules
L The value of +he key in the lLeft chuld or
leftSubtree les8 than the valueof roo
Pre-order +saueTaal 8
The value of +he key ih +he iht Child or
A,B,D,E, C, F, iot Subtree i more than or Eaual to he roo

2 Inoder TgauevBal (L In thi's 3The Tiaht Omd Left Subtree eoch

Subtree is
raueral mthol,
+he Left mupt also be a binary Search tree (8s)
loter
frat, them +he obt omd
Vipited
+ ri ubtree.
Algothm
ae trauersed-
Untill all nokes
toverse Lef+ Subhree
Stepl: ReCuTBively
Vi3i+ Too+ noe.
Step2
Step3: Retwrsively +roserR
Riht
Subtree.
 (aToo+

Inorder Taserzoal .a, -

D, B, ¬, A, F,C, mathed
Trasersal In th'
3 9 Pobt-order the rame
Vigited Lak, hente
+he root node iz
fir3+ uwe tvoerse Left Subthree, then the
h e ToO4noe.
riSubtree omd finally
Algomthm
are
traserSLd -

Untl Al nodug Let subtree.

Step ReCuraively traerae
Subtree.
+rauerae right
Step2: Retursiuely
Step3:Visi+ xoot node.
roo
ex

Popt ovler TroseBal 1

A
O,E,8,P G, C,
 Differente be+ ween Stack Cmc

S+aCkK ueue2
Collecthien of
1 I+ represe nbs the Collecion of
1T+representsthe
Lat i'n fi»t Ouk (LIFO)owkelemunds i'n Fipt Zn Fip4 ou4 (FIFo) oxder
elememts i'n
are i'nserted oamc
2Objectp are inserted amd
2 0bects
removeed from dfferent Encs
semoved at the Same
end Called
Called front omd r e a r Ends.
Top of Stack (ToS). Called
operation
I n r t operation is Called 3Iner
3 Enqweue Operation.
push OAeratn.

Called Delete operation sCalled

4Delete operotlom
pop operatn
Decseue operoatlon
In Cueue there is a
In Stauck There ib
no uastage |S
S Space.
of
o f memor'y Spoce. wouloge of memory

6plate Counter at Masmuge 4Students Stcmdng i'n a hihe at

ReCeption i'san Exo mple of Stack fees Countes i an &rample of
aueue.
 Diffesende betuween Singly omd Doubly inked Li'p4 62
uLLLLIIZILLUuIILILUILllitiniLiLLILIGmITTIu nIIILULLTIIITZ
Singly Linked Lis4 doubly Linked Li'st
1 Singly Linke& List has nocls L Doubly uked LiBt hos nodes
with data fied Cmd next
Link with data fteld omd tuwo
field (foruward link) pornter field.( Backwerd ond
& forwerd Link)
Dato yt & revicws Doia Next
2I allows trauersal only I+ allow a two way
+sersal.

3 T eqpires ome L poiter3 I t rqures two Li's+ pornder

Variable (Star+ amd Lan)
variable (Start)
4I+ OCCupres Le83 memory I+ oCCUpIes more memory

S Complexity of Ingertiom amd S Complexity of Irertion owd

Deletion a4 known POitom Deletiom at known posdiom
On) O1).
 ((%s
Dfferene betuween Lintar omd Non-intar data Struchre

LinecAY data Structure Non-Linaor dato Sructure

1 Tn 4h'h dota S4ructure|1In this data Stsucture
The elemuntsare orgonied data t's organized witheu
t'n a quunce Such as Oy Secuece.
6 Aray, Stack, queuee& Tree, Groph etc.

2In Lintar datu Structurej In non-Linaar D.S

Single Le i involued.multple Leves are invohed,

3 74 is Easy +o 3 I+ is Afficu4 +o
mplemand.
implemam
4 Data &lemans Can Dota tlemunta Com'
be hsauerael in a be trouerAed in a
Sngle Aun only. ungle Aun omly.
SMemery 1 no+ Smemory uhil'zaon
4iled in a &fficrert 'n an £ firent woy.

6 ApeliCatorsof Linar |6 APplicatons of non-

D.S are mainy in Linaar D.S are in
APplicathon Software AyHicia Intelligece
developmaw Ome image proteAing.
 Diffexence betuween Array Omd Linked Li'34 63
ZUITLILTLLLIIZTIUTUTTUU TTiTUTTZITIzIITIIzuLz

ATsay Linked-upt
Aray i tixed LSize of a Lit 's not fixed
1 Sze of an

Collecdion o
Collection of
a Liwked-Li's+ is a
Aray a
2 Homogenesus (Similardala type node Cdata 2 addres)
allocoated froom
alloCate trom 3Memory
3Memory
Stack.
heoP
i+h S4atic 4Liwked-Lit work wi'th
4Aray work
bymamie data Strueture.
data Structure .

a r e Stored i'n
Elemanks
5 SElements Can be Stored
Comtigusus memory Locohioms.
Cwy where 'n the memory
6ATa Elemanbs are i'ndepen- 6Li'nked Lis+ Elements are
dem to Each other. de pend +o &cch other.
Assay 4ake more +me, bLinked-Li3+ ake Less 4ime.
(TneTt1nL belethbn) &
( Inser+ion beletin)
 Difference between Tree omd Groph 6

Txee Gasaph
1+Tree is a Collectiom 1 raph isa Collection
of nocus omd édge.
of verties/nodes amd
& T: inode, Edaes 3 CVv,ej
There i's a Unuaue 2There is no unique
node Called oot intree node.

3»There will no+

3 These Can hee
be amy Cycle/Lops. loops/Cycle.
4Repreenta datoa in 4 Represents dada Simihr
The form ofa tree Strutue +o a utuwork.
in a ht'erarehital manneY
S In raph n e or more
SIn +ree my on
path betuween
Pa+h between two nosestham on
two nedes.
Zn this Preorder, In +hu's 8FS md
In order Cmd Aostorder
TraeTbal. OFSouersal.
Ex &9