Scribd
Upload
91 views15 pages

Data Structures ShortNotes

Data structure gate exam notes

Uploaded by

maasalamix
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
91 views15 pages

Data Structures ShortNotes

Data structure gate exam notes

Uploaded by

maasalamix
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 15
i "ReRAY? Clas R)Rew majox Order WBynarefoncth) — ARRAY | acld CACIIT{]) = Base Golds + # : eign 1) Finding min |max [Ci-emian + (4- cea) «7H @ By wimple traverwa s- cotumn Mass Order noe Olay eon Ode ALICII) = Bare actor + ® Tousna 433% [d-e8a) €m + Co- L@i) Vx sRgeF No} SE care eee nyo WAU mutt dimentiOnal arsvcys Te= O(n), SC= Ln) Gu stettal iN 1D ayra Sine QQMsI6] =X ~~... 4 Is YIN ON ory Mele, min tat climension ih epnsnar “ a oe ware 6) Sp atray:- ALLE, UE [UG 48s] (Bs UES] D Fi e wy, +. i No-Qf 2D NO Of WOW COluns DF = ae ee eee ok cd CO Tmesing RHO ( " “ Same {or LL nai 24) QcLALALC ICICI) = BOC Odctr + Bereta TC=Oeny SCO [Ci=CBi) & xe + (4 LBa) eS + Uy-GB A 4 MAINS And min : 18) using CHO ; a ae ’E then ano min Oda LALLA) = BASe aaloly + 5) 8 Comp = Q-D+(7-a) -ancal Wl-cedeqy + (x-1Bs) eer + Y= CBr) Jew! eng ee Ge ms Slower ttOngulay matrix Comparcot tsitn ye ele HOS GAlAALITEAI) = Bae acter + NO" COMP = 0-1) 4 (lepn-1) = nsiegn [Ui cB Hitysat + (47182) Je! a yp CY gsi) Searschin, eran DEMO? Oda CALHEYT) = Bare color + Linear. "8 “Binary Ga) [re S850) —(UBur 4 1) SNS + Cig) Jew TC= 0tn) OLlegn) 20) Lower A Marx RNO= UpPYY A Matin cro COTO abr ATH _GtOt = Gf RHO "Gee inalise on Sorte Lael" HASHING, Darras is staccato stracrure, WSEAsChing tecany 4L B® dynamic. W)DNECE Gololress tel rkey ib addsess Jint an}; ine aly, qu woreng, “Stach time= OUI) (every core) Os sige UNKNSLON. “DTQWbACKS tNJinite Kise ACU, teubLe Asay Name i bose aololress 3) Types &Y hark Junctions :- 10) add Lar¥ (tI) = Babe + (CALE) msiz4041 |@ Division MEdule Method (kK matm AME Key=Cio1o ) aDastay s+ ALB uBJ[Le2 UP,] Key med m = 48B k die NO Fuk (m) = UB)~ LB: +4 + Pxeev im votue prime numbey NO: 8 Column (n) = UBa- Bar] NOr Uske TO Qk, dist extraction memod 0 elements ?n Tange Le-UB INS A mee ett" Prope + near carn Ora square meth SY Key thenyspacr Wtf atiOn = NO- @ ccupica A/D Anal addters from middle elemens O Si % Meee searching tim = Goll) Gian B) Linco PYObINS + "8 bh) UnoIM, abning: cach Rey Aas cqu Lp =(HE+ ¢)med m 7 AC. 20 Probability OY ging tO any K=OUDFO(I+0h us content 3) SUCCEAEJUL StoTch fos tt ttm = (nsocting tte fem in tabu UnbUCCeM4Ul SCOTCL Jos ith étCm wit, (1 cee tN tbl. Sus (2) SUCCEBJUL ACOrCh in Chainé fakes AverOst Cade tina = ihe = I+ Anée sheen) Sle a 93) IN Chaininy , AvEercuye CAL time iW cComtant “OLI+d). Ki’ consrante whtn m=oin) unbuccessut | succeagut | chairing = Ot) OU A) Caderewiyy OCG) ofl) | ant 2) 30. chaning Clee Ore is easier be ih Tet StS “open. Cd reskin in PrOcing ch OlefOuutr ‘4 fi p r caruistond hosing eeani (A UUeseal FEAL » ite Set s = Hnete AG “E 1D Dynamic WaGta, stsUctUNe ae Le Je ACCEABING Unini MOLrZe pornees os id ee Ss May: NLefn in) Cue place Uefa Mauer Ketutnd vO'd poinne — *HOLADTE ON LL cA. bette! thon ar ‘ 7 np 5 Cor thoes vohy typecasting needed 1) On 4, au sores | jo CON be ~" MEMORY Created udtre mastec 12) Reverse GL % TC= O(N) CEC) (pein? 4 Created in Heop dua i Pane ex aes é c Kh) Rincling lacp >\TC- om (CO |?) Binary Story i Pessinu er ae Lc =U) ecitrc guy ged. LL bUE ith NOE e{ifcfent- ETC $lO4 -f 3) [J Hux frceis) 4 {7C= On) wing £7 RE Called Aanglingepsintt: Lsc- ou ¥ Pf(s) ~ 6000 yD verve Ceanbit , ete ALS data» Garbage lponee 19) B delek 0 noo pointed by de Pi Gana) > * oe Pointts = OLN) We) OL!) Ge) 14) J _S=Nvu er S-s0me omeradti6) 1 plelek data Gr NOck pointed oy 57GB Memo 4 attocolol Bivtn pointy > Ou) Die Com ONAL ay gp buck in circular L4 > DUN) CohleA Memory LEOK 7 CHEE © ol ae SEA) Finding 2nd (OS Ch in Circuucr Cloub S)unien a 2 LL > OLN;EM) |? EEE re 6) antersecin ef 24. > OUeNi) gig det 4) Apencling £ LL lansest YAbending £ LL oF enol S| Mis atcston Dezenion, ou) | oy 8) Binary Aeoxch on LL Ot, -H AE beginning | | er Bow CEES COMY > artes a give nccle an a Binory worch on Arway = OU) Best cu 2) BYot G Bien Node ota) | ln) Of iepidwornt, pug 4) At the end | oun) | an) At NCO AeOrA on LL OF oat end ( tart node ocn | ot) 20) Betec) Ocichs es) given) i OCn) Ge, acy) 6) sorted Lat om) | an) oln) 9) nesye Bot On LL 4) Of @ siven node rein wf Doubly LLé SC = OC Lon) - xed T)At OYINAIAG 1) Merging moo uae Sanaa an ned Snplou. poe \4) At the Cad Te = OLminim,ny) (BC) At. the tnd LLatt ned can be [my nt i A Peon plemented using” ices given) eFirdife un Zuck ele on Ltr thor 6h sorted 1st Ou (hxr thon LLindala +> OLN) +) gy a even Mm te Checuulor LL & (Singls) A GYUUOT doubly LL ke: ane # In Det Insert, Deletion. tnsoution vac T Ar beginning oun) ony ot eo oc 2 ACHE O BIER nedle oti) ou] ou) ow) gintien £2 b ByouG = * ot) oun) 00 oun eats. He Ae endl ln) otn] ot) OUI) (by oleteeing na is AE ¢nd ($Oslr Nook 0c!) ; ou) Sie sen lees Given) om) oh) RISTO deleig Sn 4Ovtcd itt Olny ou) otn) olny Neale, te TO Osiven Node | On) = OW) data. “Emp i ebtes Barn ky FESTACK, a SfGEK Usree tO, Cheek povan theses cxpressien YALEO / FILO propesty | ¥ Sue Using stack ¢ 2) Push utingasvn) FOF ENGL > 1 SICK Needed 2 TC= Ol) A ¥> OU) (EC) RBCS For dequue > 2 » “ sAine ees serunnire 8 ‘atoning | Gie- om) we * NUL Pl tacks Using Aingly oll) BC,AC avray t jeOueut UW Uneterflow if 40% Si4 Sa Kth Stack énitrol cop y |, O% ©: Onety : 4taUC= (ic 0) ME 2549 aitoy K Stack Using OUCUL; (Lineor Wor) ing ah Starting sibck ME No-ey 4, no, bere 0 BtGcK st aw full Y Te MiHCL COP AY sI0ck Sit) eStock Sk emply g T= (niniat WP & slack s * Push POP > O41) ec) X MULAPL stack waing Single Attay efficiently 2 “Stace a fuu y Tet l= Te * dey Stock empty Y Ti=-) Right = 4 TReN 2) InseshOn & deleH'on ap tOP (Qk 40mL end) | ¥ difthing- Pwr 4One Kee tood, | POP fOr Ke Phe KQ time jo d Ancor queue suquireel * PULA > C=O) EC Uke 2 Pop + TC=OLN) EC omy J+ J) A1acK B Cmpumented Uding | Livclor Gueur ef 4x0 OF 1 Uneos queue & inginike Aine TO Op do: M-) D6 , O41) EO , dO ne Stack Pee mutO.hOn : eNO: Of Valid PeemUrGh ON wit 0 inputs = 2 MS Q invalta Perm = ni- anc, * cakatan no- Fer K RECUNAION e Hecn16y : PONE Ofer xecusaive ANON TAL = + How wesk aytey HecuvAive Cat S for the given xccusive preram , on writing equivalent non wecuy dive pygptom gap. wap ge A. 4) avg Nifetime EERE) No | ek én ALOCK X41 OpCrANEN time (ra fe) Yo ba blv 2 Opevanion a -Y stdcr atmese ehiminakd 2 Tt Ssecersnion 4] Ataoe 4 CMe Aanu: ven ~ 3 INLCECE KECUITAION + Gocaliny . cand Cate efor TC consider TC Of thar fur (A/a) AGVENY MAK NO: BF Kecwvarve cay, asin Nested reecuvaion Ext ACM-1, A(m,n-)) # SniN - Prefra PSsee: aye @ \ cysion AON Qy per PHEXCEY and assciagivity WES assecianvity os * Sik LO POSeAX UL 2 VOpesana 2 PYEAE tubing stacks separates spwonity > TWP Prigtity=TEP + Yasyoc Ree thea puie Yasser 2>R thin ine PUL mn, + TC= OM) @perares stack roo 2 WAN C cOMeA , PUK 5 tin (comes. © pop C. J computers WOTK with, Posryix expression. 4) computts converts RITA Ve DeArAx expression the tvaluak using StQck. S$) Evaluation & PRAHA oy i aT using ACK, K eperank £10k 6) Sn posthix stare maxing Ci¥C, rom CHS One Prefia 400m RHS DNS Nitta E BIAcKEE tN a Fibinecee Sevics 2) TON = TUN-1) FTN) te »TC= O12) EC » stack A pon =0() Fur ca > Preorder fur completed > Poarordey ee addihion tants place. prev ACAr fur CAEL, a ikon thew. » Reema. AEAHON 4) yo BEE Xight tS UdE ’ P a_& posth ression: rd e dle 6 Ascencing PrOwty Oueue ABmautae ele > Aighedt a ing PviOxe SS neat Se Priestly 2 Smptementing eo pnonty Ou # Towers SHANE « Te Aas unique TOH(N, A,B, C) gba No: isk tower sy tra ce Oy = 6)NO Of fur caus , FEN) =f FON FFD | L yo no ok BY Ader, fn {FM ° t {ND ¥ n-oorl sQuhan ges min moves ce Desh’ination wes vnits miliatory Wwer means move n dak fmM Wuer Awe, 2 Te= 002) > Prtgnity< TP ope fen pure ) No YJ Moves » Fone 4 figher # QUEUE )snsetvOn Ano clett’On at clivunt ena win ) comes , POP & PFIAE ay EreQ jLTLO POPUN Deterion® Fant “ fuu OMly 1 ekement pyaUUe 4) ENQUK 4 Te=O0U) EL Degen? CieculGx Oucue + y URtI) mod N é >Fuul y feecl > Empiy Priority © Descencti’ Largest io onbor teal Qsecay 4) In 409), attr Nt! fur coll Gi) Sorted array (i) Min hcop Oucus * t Oucut empty een) Hh an ati) on we uy ee OL bejn) we ou) “~) S ragerton OLlefny we Dajtes Qtl) fur Call, Ise MOVE COOK Pla. ee » Stack 4PEq = a 9) Nor & fur cats Fon ={2F00" ae Lo fone fim Bet oun) ou) ou) be 6) Minkeap bebe data structure |B) HUGH Of Empey © tree to 'mpumunt Asc Priority Oucu,| ~ " "Oe nacle = O 4 Masheap for Oese Priority *. |) © Jind heise A given binary tree 1 Priority uc Bp EES Cteos Tc= OLn) Gute aoa nor Obeys FIFO | apausfOln) — we Propo Staut APau | Ol Lsfn) BL,AC 0) Heights max clstcinca from nile Le 8) vip Hestricted Oucue tinker On 2 Ror DelehOn = Front 4 Ror | Atvels Number Of Parent corvaponral 3) Olp weticted Oucur | 18 given dk (MWeyOn: Fyonr 4 Ros I) Stvict Binary (vets either 2 OY © Detehon: Frone | 0 child '9) Doubu. ended Sueut Locqut) jay verify given vinary tree U eMBCVHMN + FrENt © Rear | strict BT: Deletion : front 4 Rea | Te={ Qn) we eee eens Ou BC wot Aat Only { FF TREE ee chit : aa |® Disconnected. 4yapk > forest # Binary Tree Wwheri CCA CONNeCEA COMpENENnt 1) Every node Aas mox 2 Aiden 3 atre. 14) TO veri i ‘y I) has n& childlsen —» Leof nods aera given 2 Brnary tree equal Remaining nodes > internat no Tc = f0ln) External n6de/ze af nou? B)D,E pu) ae ie nal; Ac i nen, lea nerde/EENET ALS He) Te convert given Binary txee NOn eh nodes = “Kolar NEEDS inte te mitsoy image We 2) Sey Ryesc not Data srsucturti FE Ou), €G ' POIs pointing tO NOdL Y AUMNOTES for every kecUTsion, non- Atucturt. | XLecursion PEL bLe. 4) Y (HOOF == Mm é le Tee Ee Qli TRICK: Y 4G uit) > Empey Thee Croveads _, PRK; drew aoe |S) Hoke Aust ECEMINAatON COnALlihOn|L) Preetader s NLR - tod COMHON of TOORZNNUI. | Postoxder : 2 RN Jareomm ec non leas rods | Snorer LN R J Stack fouggn) ec 6) © count no ¥ BGO GO, 1G. cn) We binasy trees 8 '2) Preorclex Sepuence 1st pode + Te.= OG). EG, 4 POKrdrctey Sequence Lease ndale StOUK 4 POG = JOLLEN) BCA y B KOOL aot. i O(n) we YT owarreinary ere Lwe vequire é either ( Presreley t ONGKder) oY » Tata 3 Wostordert INdrder) evel = 4 i ; Te=fOne) wo devel= Height th CY Be > Ae laygnorder troversial gy Menoty aN AN 4~S tree & eB. BL \C (Be es Let YOOt > Hédelle ~> Righr Pregxd Inevdery Poster = - QO: A n-ary tree in which every Weonvere preOrcley? NRL = enternal nods GA cracHy n Childie COnverde Inoicey + RNL has w tntrral nodes, y° leaf neces Pee occ REN ahgrte of inttynal nodes crupk ‘Ao A A. yor Bw (NI) 5 4 Gs on Zz, aeste leoy node UI 5 OD B® EZ wo" Oo Touaree = ae COn. pre. con.In CBN PALE one: Galt = A(UtY-1) 5) Convene pre <____, ines POSE we COnvoae Past Reverse —> Pre. “a paspect /complele. BT C7 oe build convede Ing ___ Ta given Gn | troversCL, : In [prcipoae S)FOM CPre+ Pastendey), we will get x Full dT 7 ange ov GF fn/PriP onique binary tree Only “EE thew = . » L Lest Akceuteey a most BT ‘er IB) ExptessiOn trees a Oxbte a, < TB 8 xh dag se - ~ Nx Ni a | 9) N-ary tees COCK NG AOL Max | N-child¥en. lo) cOnvecting n-arv tree Sns binary ee 3 AGE MBSE Chilo - Right Ailing a. a | oY yg oo mca | c Pil mom .eh | £ ~ tee noce . | co Et bc | ; (= N)Q Pres pesoscey a BT givin F Dare teers 8 gina, to verify 41M eptiong. 1 We Can OVE Unique BT rom » Feneucing combinanons : (theta) 2 Chasrgais) , Heap mestacompteteabinangentice “el heop: Parent < chilcl fax Acaps Pavene 2 Chilol DAvay veprascnearon ef Acop : Paorene (iy= /£ lye chila Le) = 2¢ ( Aigpr chil (1)= dit! inetex Atasti fiom 1 7 4) | Min Aeap Max heap nim ele) REEL OU] Leay tx) Max ce | leay pin — Rest ol) S)St i Q Acight balanced tree WIth Asn levels. 6) on compicie BT LACAP) » NO” ¥F leo nodes Non lea} Nedte (Internal necte) =l%] NOTE: AYTaY sepresentatiOn & better] “~~ gos CBT & gov Kemaining LL iB etter. So xeptesenr Acap using antag. ¥) NO- Gj eOMParisons neccted 8 gi min in Maxhcap with _M edema} cy Max in minhtop= a) SN. MAKACAD, for sinaling (conutansH max Sn minncap. jor gcnding (constandty res constant no Tc =o) Comparison g) SNAvttON in MaxhtOp/Hinhcap TE-fovtegn) WO,AC ol!) BC . Algo: insert cu Lab £ O16 Aeopifyp ja) DeleHHEN ALGO: ° Swap TOE Node with LOSE ele eDELete LO’ nocle(reduce 4ize) > PexFOrm NeaPity aaon hm seoe| Tc= ae? we,AC ou) Bc a) By Ian Caray OLN) Apply BuildhtePp Method 2a) 7 delete Cw pSsition Le mom Haxs Hin, ACAP TE= OU) ol) Be yandOM acces goto CT pasihior SURE! by last made» Perjosm Aeapisg, UP 4 clown, c4n Q SOTA corey TL WO rnd pate J NO. WALL dom | is >1000. LEX 4UM 41000) TC= OU) | BNumbee Q| heap with rn cles tinct Kegs. pone of cue en Let gue tree, ns eye (First construct cer with no * onltibelea nWales. RODE & dix: _min or max) KOPtMAL BST : (weighted BST) is a BST thar minimize search Cest (NO. Bl cOMparis Ons equ ved tO Atarcw “gor a given Key) EX: tp: 10s {rey = 434,504 10 2 Nia Z Gost = BUeI + SOL = 134 6 cost= SU XLT SO =1IG min. RoptiMat BST cankrvuchon con be peryormea efjidcnrey by Using denomic PRES Yammi ng: FCO — aoe +t re eal ht R=N-4 3 ReN-IHL Ne 2) NO. Of unlabeed Binary tx # BST [rarer sce BSTew) ~ TBST SER) as De tit Ty n' nodes = ccralon no Yonexdce of BST & ascendé Oxder- : 8 9) TO COnvete GN UnLabe a TO ger S0Orted Ovdes from DST therca Only L UNIGUL Way. Bsr = Tl- om & 19) TS convert Gn unlabeled BT f i 2! ways 3) CONgHU Bsr we vequire (MO. PIDCN 4 WEbaands ade Cither nn) MO Qf binosy tYCes peMible DS ety Ake @rder tO ger inorder. With M NOAA = nb, unlodeled sn TC= OC NLeAM) + OLMECIN) = Buntegn) ving, en! Wort Bingseater cack moor EC = in in@vder rr mani) On OST sBettey Alos Wsiny Stace WE a te > Right Mes Node Tc~ for every NOdk conten © Hin Cle > ket most Nede Ec) M0. &Y Compo: (69 top bag aaa (otha Max Ue» ROOK} Max ele OF 4) for G given Preovdes of Postoiar » max & tye aubknee Yoo ae © Citak BST will take ON) | And min th > ROOF & Min Ch or Min OY oLighk Aube rE Y Min Ele - time Ec) 5) FOr O GIVEN _preerder, dlivectly stat} i t ‘i Pere elas Ber qian ares. im oe es ch in Bsr for Postarder, stare 408M Leibe- | c=fOCn) we 6) Mox_un BST Hin in BST od) © Be | (tan) AC lyr , , Cc to find SMau est element Qddentily coweor sequence for | Be | we AC aaGuns 20 IN BST. | eer Be | we | gcd: 12 5%, 60 SD n | 9S2O $0 laut “ete ‘ater 9 must be Bsr | 1 n | dein Steater than g becay Ux Will a | Ave | ten ‘i feo tO stor Bo. Hinktop| ae 4qn i sey, S 1 PSB bur soca SP all muse be) Maxhiay ny n n «howto JS) TE 1 Acorch On elements Be 1 we | AC x * N-o8y Tree: eorh | In: bacde Bu a ae wt Bost a ft abcde | esr | t n | sen Rae PREY bedea | Ave 1 Ln sgn DNO ef BST PossibN WIR node eniee| | oe = cataton ny. = Maxhtop| | n n NOME: JJ AsKra t© clelete NOde, chetere thar particulos NOdle. Y Ukea t cieter clata ,U con su plau dcua Gnd cletete another nod. Lofn A AVL Tree + sey barandng tree gp Height baton BST. © AU tite & BST , cach Nude having Patomcng facror —1,0 oF tl * Htighk= 14n (EY) If) dnkeetion & G node én Bsr» BaLOncieg factor = Helght (kee AUbtree) “en Bc ~ Hergnel Right uberee) otn) we Joan 1) Foe max Bight whit. given no. Sf nodes i HE le ae a Pei acets ars tel i feat BST fo 2 find min no q nodes ) © 7 prom n nea Sy here Ih 16) TO Confirm ele % NOt Preacnt * 1a’ age eave 6 fusm AVL toa a we | Male lee Aneel tree Of height thin OCndegn) AC, Be baton it & count no: | neces.” 18) Sine. AVL & batanceet gsr, ® fin Aunt Mf On imasanee Csr ov All) TO creat AVL from n n Tes OlNLe¢n) EL eo ly Hin no Of nodes viequirtel to AO 20) Snorarr Auccemors Mim a | AVE tree ef aight H fora? Od ghe subtree U ie "snevder predlecersort mame ae iniNicri=t)sreit ANG 5 HPI yt subtree TO find succ /prtd : * ROtAHON: Te-fou) Be (wea, °4L Femme wotation Te 0U) ot) we engin °RR Luan) AC ope } oad rotation 2) InsettiOn Glo: starch for | “ ree Caen oO ceed wonow 5) Sméeree Ga te in AVE & pull JOundh trdene » Te= Olean) €C \e)ansextion A Always at NUL. ea i Tai 7 ing SACK « Uta} Node => ClinecHy delete |t) AYtey | non, (le going © node with | duld > aeete& | 6% Pathe Checking for Broan, ink | Chitol NOK | probkm =» min Oo @ necle with a childl seplaUr| HOA 2 HKOFAHON, mnd With inorder SUCLEAOT OF |g) TO LUC AVE ETee with 1 Nodes Piedecosor , Celere ‘suc /pred Te = Odden) €C) Tc~Jol") Bc (Ceo 9) In AVL ttle, oe oe on) we Gigtiatt§) Finding O nods with 0 or! Children OUen) AC. He > Tc eee EC adn BST 4 AVE, insutiON is done at} Finding O Nécle With 2 children WOW LSE Moy’ of NOLBEMLEOY nce ) 3 Te= OL!) BC OUGd) ¥ Jo) Delenon 4 TWO) IN Bt tlc, QLt Keys Ore psescnt in Leay Mdder 56° SeqULNhGL U) Apity Celetiny ny towards weary Cn GKO be pr fosmed. bum COme 48ve 1) y Wwe a . splittry Lecy nocle Maintain Oey aE inosaer SUC/ Peat Place problum tn woy. W) Height & B/ at toEc (Ol a2 Bo= ns prbum I) TR SGTCR GN ele en BiBrete | I Te (© debe an ede er Ave Te={OUM leat) we 4 i : : : Ou) teee~ Ol kegn) EC ~ 18) Sn we ymax no: of xotanon OE A Mig nor Mow a Sphon, Ales cuteting cin eh ise ae 24 MGx Probum = algin «gg SnOxrder bs Ascench'ng Order. 14) Gr Gomme 2 Probl Come is) Deuton AYOs 5s ent whi gS worthy Ont WAT faoceess HY CH iS PORE EY Lec} Moots, Cetete UE ens secant. BiSere J underylews b8rx0Ww fan srouiny aac ie “i sega ov “Combine. Bs Bt Tree Hretatenen, HOLS Tee a J theo net pave, feo} node tua J) These Ga ACO tree Ake | XI with indYder Successor: Os _Preclecemes thin olelete est 4 Av. it 2) Balance trees # AYTGY HEPSCACNECLHEN a BE Tee + | Root inelexel 3) Y clay =M i Agt child ce i max no- FY Uvidsten= mM ca = is i oe Min no gy wwlaren= Patent § nek v = g max no of Kegs= ml comple Binary tree: + eda é rein rie SS []-E pom tur to lt es Sah te 4 on N Full Bina tree: Cvexy nade D gaan Sagar 08 Ot? fal aah eh! a Pevfeck BT Aas evexy tevet ust: 8) All deaf nodes Cu Cit ed foe Level. AY an Ver flu > SPIE | ‘ pe ene eee | complet 8T Fue Br Pevpect BT puie | = ghtl ea | Fw of nodes = 2h =] hugh ncrease ©9 foe Keighr & NO} deo] nochs = NO Q internat A With a cniid ren +1 @) Te to (nsest | che easy (EO ae K Force binory bee oy height KR 9) Bt Erle Cakes mow Space Hak no % necten = ghey thon B Erte: Hin no = la On tevet © ay binowy eee, Amos 21 # FoeO comple BT & heignt A, |HE GROpA HOA ND | nodes= akt=} | See Hin nd OY Nodles= Qh 1D Sdepree en undirected, GYApA = Ak ~% TOtat no BT with G givin | NO” A edlger Pre/ post ox cnerder Ayuene |* BES /OFS 2 = 2%, Te=OLVtE) acy last UES Se Shelly er ET | OWA) aaj matrix # WUgAttl Path Lert, Oar (* BFS/ devee Order CrOveKsaL ¢ j ao : UUs Aign Vo =rSC=OlV) © Z URAL y ny: coe: 4.30 TEs Graph eravedsal Ad moe ETOVERNCL 6S Unique |) For evor FT Oxdes, BET tnee exe Bat cane: certay size sequirea | a 6 o ae =N fus COmpkk Br: Jk Connctrecl Acyclic Graph @ Tree EH i A GoyLle WOTSE Cod: OVaAy xize= Beye *OPANNIN tYCes Connected acy fon RIE steed BP | Gop Raving cut vekercen (cauti FT é CIC Y alt some) * dnany Binary tree haa Ot. BF 4 ) TO checit gxaPh & CENNected oF Ne | Te= Otvt€) ad (et NO 6 copes = NW OLA) Qay marnx z U eachabl Or Ne © Desoun hn + 9 Ancestor aha Te otusey ady oe ¥ Level oTerr traverscd (BFS)qBF ow) Pe TC= On) Gust ue 8) ddentifying nO YF cOnnectect componal NS qe SC= OLN), od very tere -t0n Bor OF NS & SEONly cAnnectea camponut 7 a f ip TC=0(N*): busing YecuLesiOn) T= Olvre) “ Qag (ae pres SC = ON) aoe olva) Qoy matrix Se eS OME AS Get F 4) 10 cheek gven graph. contains cycle Tre > ag OF in uxtightea gvop, wit Ody Ce te Bese rad OF ve Finding Shorte Pi [Pom a Given [ar SP CEO Li nnd vecrtn eS) VOY OPEL Yow, ho in Forge (Oy OI oy coun Be TD chtck given graph U "Bihari Stee MEAP ERNE oem OF migt 24d au veeticek OF @ leved in’ Oru gy TENCE Bene teDe fet Shy, bet 84 FEE bo inanace then find. THOME wore, By AYO COnitder Qojjedist * Full binary tree / Strict BT/ Prope. BeYONgLy CAnnected coMPONLAL- Oe eae | COnneckect GsmpoOncnk usth divechonk Lert) , NeIte ro een 2 TC= OWtE) Gay Gee > N=2r¢) = 22-1 ee OW?) oy moevic N & always Gad DGAC oa) 2 NO} PWR = NO pop = 2 ON BFS, Ne- yf tnsection en Gude = _| NO Sf dee hom = V ¥I-T8E s CCK NOL has Ook . Children. Max stack digo Ne pep_in_biw ¥ Appuicarrons a QEL + 4) TO Checle given §¥aph & connected or not YT dind no oy cennecttd cOmpantnt NoTes DET Cone be Usel tO find ShOriest Path cn UNwelghtecl gFaph - TO detect Cycle. TO Chee G veruk cy oO nO FOM % given TD Check given chigectect §¥oph U ArOnsty, cennectta of Not ‘apply DFT S Revethe cages 1M GYaPA j Apply OFT © ATECLUGH'ON peta! Cur vous VELOC Cul Vv OetEK CFT Cont be Ua ) © For evOLy Connected gxaph, sPanning tvee possible ¥ Cdge Chassifccarion: « Tree coe: Eckyes present in BFT/OET tree Or fosese + Fomilg: in tece, See O§ node from AOOH (D Cah Leo] BLLBAY © a Jamil * Pror vortices Gtk ancestor , Mere VeLNCes Cun ClesCenaed . * Bock ealge = ana Jomily edge going from G vertex to i onctstor. Bw pteaent , theres Cpls 2 Formoid coe: IN a family cag G verter 19 U4 Atscended. * CYOSS edlpe: Neither forward nor backwara cope, 2 eifliclacimgiek. ACA He byped Q FOG colpe, Tree eclge, Back cage , CoOKS caye. 2) DET ona ¢, hh Tee eye 4 Bac ¢ i ge OFaPh hay Tree Coye, Back cope 4 cv ¢ eae cp He Coe a ibm eee XO 1 Min stack sige TO fid QU Grbculahon point | oye. ax Pep Sy Jn BET Undliscctec! GrOphi CHOW —Colse, thou, Cyc 4 Prekene> A>b mony & & coltcint 08 | AF PROGRANNTNG Code Section | Cae —| Static... aeuie Section} Bend Kuno’ 2) within @ {U" avGriGbles CGnt Rove 1 40m. name ol (9 Static Scoping: | :8Onu by cBmpiter OF compa tine “ECKL GIOKOL VOMOBLe 4) Dynamic SLOping : “dom by PrecepMor At YUN time. *tOice COAT Om cn AtQCK ,G ndi- thow then tdiu glee voviab& Y Globat vol Also not teu > evsoe 5) Every chor CGin bt Arorecl AS a int bur Ok Vin versO. (chO¥=18, ‘n= 2B) 6) Gidbak¥or wu desrvoyed Gt enol Of Progam , AAVINg MAA si Jehme }) static variable + LOCAL vatiGebl in Atone arca- 1B) HY take Keyword & Usa With from)" tocar variable» Memory cs allocated or compru tinw tn Atahe wus, IS) Aine CONCUNING SEAHEC. Key word A excited ONly ONE Gk COmpit: He 10) Q= FOO , Frese POU & extcuted then CUAIgNEL HS Ce. ll) dn tnt O , chor Nor, float 0-0, Peinits Nu. IR) Zero UU FatAe , ALL NOY 300 & True 8) operaniun GU dorm blu Operands WY same clatcr bype- M4) Right tO tet corcceaavityy : = wl, ras plz, SEE. By tt nyt oe, Leype) /SRUg )

You might also like