= Qytt-T BAstc TRAVERSAL AND SEARCH TECHNIQUES. —_=—_-— —- Techniques for Binawy Tees — 2 a Binary +xee -tvaversal + there ave rary Operations that’ we want +0 perform on nas trees (Node in the tree Teavessal techniques: There are 3 -tupes ag tvaversal techniques ‘in binany tree hey aye it " Hraversing a tree oy vistting each exactly once” I Tordes traversal (Left Root, aight? R preorder tvaversal (Root , Abft, xighd d-postosder tyaversal: (1e¢t vvights 000) Algovithm streenade = vetord: “Rime complenity? 0C5D 4 type data: tveenode x dchiid : “Even ode « vchid > & > ‘Aigowithm Tn0vdey (4) Mt isa binary tree ig 440 then Inosdev (4 > hekind)5 7 visit, . “Trower. (4 > schind, ye > Algofith Preorder Ris 440 then t Visit 05, Pre Ordes (4 > Lehind)s 4 Pie ordey (4 sscniid),ee rn RZ “ts algostthin Post Oxder(e) “s Y \ it + #0 then a alt ( eae ony “e t postOsdey (> leis; a postovdey Gesntds | MELO t i saint) Example FoR tnovder (boot) lefty O04 rg : stepli- visit the Left node first Steps on the lept Sulbree of each node, apply inorder vue Skepai- vidit the oot node SHU ON the signe subtree af each node , apply Inordes ate - Path= D-B-f-E-H-G@-T-8-c Example for pre owes (root, ieee ged A Root Stepl- Viclt the left Node first Seepar on the left Subtsee of each node apply pee owes wale Sip ON the Vom subtyce af each node apply the preorder sute A-B- D-€-F-G—H-T-¢ Example for post oxder Cegg. réigyrt 600%) Steply vist the leet nme -fiyst step on the lest subtree of each node, apply postordes vule- Sdepar On the Fight subtree ef each node, APpely post ovde vule | Skepyr visit the yoot NodeGeoph | ravers¢ sal tobehques: - “the proces, is cated D>we have OF -traverting OM the nos ox verties on a gyaph aph traversal’ sto -Lraverat| BES — Breadth first search PES depth Pixs search * Breadth 645 teclhriques on graghs t_ search Tt ts one of the — cimpkst algorithms fos ae) os vetting each veatex Wn a graph: Tn this method cath rele on the Same level Is checked before the seach prieeds +m the rest level- BES makes use of A queue Aw stove visited See enero the PAH Lyon ale easiest vietted vertices Algowitinn Algorithm Bre (v) Ut=ve visited vd 215 Yepeat for all veekces w adjacent frm 4 do © te Wtehted fed then Add wtvas [uw Xs unexplosed visted [wl i=ty y 4 if aq ts empty then seturns I[mouexplored vente>- Delete the next element Us fw 44 N get First unexplored Vener oni Cale) + xyes ~derth fist seaoclh . bene anc ne. aa cane [the pre explore each possible path to 4s conclusion [path Is +¥ed In othes words as a fay oS you ean Cif you dort have a node -to visit), Otheswise, go back and try anothey wotys Straply Tt can le called ay & hack-tyacking”jah os 2) vl a el) sy gees Alggtih? me act! aie 1g Ey xa pnvore Ms cl) Q ce eo (ws Xara ysl 4 fe swe BEE co 2 phy opting pt, visitieg ane output lp=0 ee So ptbervaing, the eaing + and these adjacent nodes 08 | Quine : [9 the role that te ‘nsnited fst ‘into he widted hows then the lp ail be- lp: 0) ~Sthe adjacent nodes OF" ane shred tp she queue « | hould not be visted ia a Ques Tv]a}b igs on the above ker gee js. steed hon a 5 done on ane wsited ned @ sin ed ‘i queue queue should be [3 rm) node ts 3" ghaald be vised ofp! 013 a nodes gf's) ate OLAG «ag and H ade Hot MisHed $+ oo (SRERT] Wee 'E wh be vetled Olps 013 6 Padinert nodes one 434.5 BEE | en "owt be Ved Adjacent nodes vig st lp: 0 13b2 queue :OP tol sb 24 g ™ theve ane no adjacent nodes that ane not visited Taken graph tm toxm of tree Ae last 5’ th be Visited o- 3 ' — 03,6 2 - 0,124 6—ha,ys Raa u8 O-saB | DES example | : | ina By applying DFS 6n +he +taken graph [Dvistting “6 node then +he output whl be 0/p The adjacent nodes for | added to the 10 Now, node 1 uit be © ane 143.6, = stack F MOW, AtHer Visiting | oP rod > Adjacent NOdes py | Oe 3,6. one of the adjacent Nodes should be taken dek us take ‘6’ and now 6% > pttey should be ex plore explosing . the Me as wow Stack 7 , t > PFter a is Viddted, node “wit be exploved as acljacent Nodes ef Q are Of soles > Now let “3 + ty Ke exploied but 3 adjacehe nodes , so adjacent nodes fy y | e' wit be added 45 the Aes 3.41 Bg does not ha back +0 a and anothey taken anti wt comtaing BD 4 wetuyns Ra is ve any adjacent node of adjacent Nnocks= oe NS ad Connected Components *- ¥ &/ —— & ot “this Te an application of PF ‘ g Used for network ~ establishment mal \ fh | | ’ 1 | Super graph DA subgraph ts a super graph and no additional edge to any verter of the Super graph ts known as connected component: connected | | i L SUper qraph Peres ee oe ea corrected components in the above Superga = efter traveling Goi) vidting te aith the vertices In the Super guaph, -the murnbey af Connected Components obtained! 4s the vesutt Approach: Before vieiting the Vevtices wil be Bere ('o’)- | wow, one vertex should be visited at frst. then that vertex will be 1" AS Adjacent vestices of | ane ah 34 we Visit tw! then tt becomes I’, Again the adjacent vertices o4 Uo ane land s bub | fs aheady visited and 3 shoud be visited and ‘it becomes *V’ : 7 Adjacent of 3 ave g anda, as 4 fs alveady visited! , a should be visited then vertex >’ becomes ‘I’. — PS all the vertices ane visited ‘they donot have additional edlges - > the same procedure takeS place Until ay yhe nodes ane\ 4 didted im the given 5 . rt epengey Algosttbin for connected components: See eee Allgovithm DFS(v) ¢ int Count =o; Veta 1 Ifn 15 no-ef Todes In super graph For lint vel) vee ni vad) £ Flag (vi=05 12 (visited Cv)s 20) then Drs (wi flag); count ++) Drs Cugiagny? Huts a adjacent vertex Flag [uJ13 for each verter uw adjacent from v do if(flag [uj==0> Des (wiFlagd» rrekuan count) 4s Contains ~ Liag! flag tg used to check whether he elempn any value (ox) not Bi-connected components:- Sr fs also applicahon of DFS | > an Wis section, ux study two concepts | Avieatation point Aptecomected components tqragh) Dpvfewlation pointy det = (vier be a connected undiverted graph - |rnen an covketilation foint of quagh |G! ts aventex usho onticalotin Pott of. graph “AAs a vewter whose removal disconneds the ie graph G's Te 4s also Known as "cut point, | i) Th a “4 point In the graph to oe node qe destwoyed (or) {oma dame ocurs then tt doesnt share any ‘nfosination « | Ms pdine ts Known 05 Avticulation point 1D Bitonmected graph A graph 'G fs. said in be bi-camected | # He Conteins no amkialation PointApproach 0) eppy DFS traversing (discovery me of a node) (Dattey visiting 1 dhe discovery stme oe 1 at be | ancl 4 ae | Pdjacent vertices of lane agra TF a 1S visited then | diseovag Hime Of a node wil be a. this wil) be continu Funk att nodes are Visted and the nodes will be giver | [Value of they Af scovery Ame of tasele- (la sy 5 6 # B Fw ND S Cin 2 g a to 3 & 4H + 5) Discovery dime - i | The graph wit be: Back edges CBmoten edges? Vo 3 4 s 64 aos wb least cost ! & { 2d Bed 2 ye Wy S Lute ( ce 4 ) Exe pwcedure ee ee ee : “as jek > * ®@ 3 6 & 5 a 19 —> Discovery tyne | or ea 2 FF > 2 2 F 4 least cost nodesc wv + L chia Pareee i, rode Aerud] > aps Cpanent] 8 S513 desqy Backtracking t- General meth eHculet on Point Mate d¢se) dea ae2v 3s dese) Aw 2 df) R pax >a ATBJ2 dF) A(m eases) oie apa ey ILO] > despey ACiod > fsa} osx ye4e J ov algovithm | 2 DEN the backtracking method» Barktracking “6 a metho Lochen a pablem “having — murtl ple Sowtions to -find atl the Solutions we reed to Use backtracking » Dan the ack-toackt ne Uple (Arar hare” the Sows as Some finite set oi- an L> some of 4the pwvblens chose backtvacting ane D N- queens peoblems RD sum of Subsets > Geaph coloring *) Hamntitonian cycle | © O71 kemapsiek prob lem OA critesion function ¢ (arta -” tnetnods the desived — sotutlon ean) whee the 4 on Mayra’ in) soiutsons fs expressable are chose -fon 35 (or wrinimniyes” oF socishes: ane best done using Applications of Backtrackingprinciple of backtyack back-tyacking' «then there are possible for sottstying 3 would -form ai) these \ and save “those whith vied has the abitity +0 yield mm trials approach has to Satisfy LSsuppose mi 1S eran ne tuples force approach one with P» Me Mss. Sunckion p- The brute n- tuple — evaluate each the optimum: the backtrack algooithin the same anaes uftth fo fewes thar > the problem solving using pack-backiing Sek Of constraints a complet D > the constraints ave dassified Into two categon"s explctt x Tompticit ticit 2 Lyexpticit censtyalnts are the ules that restrict the possi ble Value of each xi, and depend on the pasticulas instance 1 of the pooblem. All tuples that satisfy the explicit consteaints define a possible Solution space for T- Examples are att non negative wreat numbers) Ex: Graph coloving s sum of subsets nir=0 wr Siz ( gico (oS WO Sie pony €x! Jjeeni 4=Ur OF Sie Satdic=a 2 ut) Exr 8- Queen psoblem 5 Emplick constraints ove the vules that cletermine which of dhe tuples In the Solution — Spare of 1 salisty the cxitexion Chounding fanckon) heorratie STEPS - 1. Build pula the Gnitial node a8 the active node Ce-node) a. with the. £-node , track the net node ustth Depth Fivst seanc method 3. cheex constraint , 4¢ the concivaint 15 satisfied then state nodes os attve nodes Ce-node) ne 2e constvoine WS not sassfied, ckclove tre node as a clead note Co-node> 5: TF 4the obtat obtained d-node, batktratk -to the -£-npde on tty\ “hen atk 49 another branch: an unt he disired — sdution “6 obtained | and $0 “-flagodsthen fos Backtracking + Recussive mn BoekAacking C4) f for Ceath a(k1€ TEAL | lgowih deal, eat EMS i 1s (BEGUD Hal sr ALK) 0) then 4 Ve (ata, “eafra ts a path to on answer node) then write (a(l* KD i¢ (Kem) then Backtvactinfk D5 | 5 i; 4 | g-Queens_prdbolems- iis 45 peoblero based on chess game with ants peolem is a queens on the ches® board in such stated nat awsang® the a way that no +WO queens can ditack each other. Here attack means no £090 queens can be placed tn the same yw same same dfagonat- when we plate the queens k the dfagonat confltcts by | couumn os on the fn the chess board we need 0 che | using the follovaing fosmula+ rape bed wv tlekd the above conditfon can also be checked as linil= |e-a] | Example: Fiest consider 4x4 chess board tp place + queens - | sowuk{or’ pw , ye start whith empty chess board» place Queen 4 on ah 2 first possible location ie 1 on the -fivst mw & -figgt Coun -- - a 2 uy of stepar then place Qa after 4ayfing Some possiite loraiions of Ga Stepae ae \ le L an nis tg the dead end, pecarse thivd queen aa ae 7 he next column as there fs M0 acceptable position for 03, | Hence apply BT algovithm and place the second queen at Cardi) location Beco ee nest araeen Mat) 21-0) Doe noa a ae aad once dead end aS. next quem 'u? cannot be placed ott pexmissible loccthon: “Here we need to back 4ratk atl the way to @ and move 7t to (uad and place ‘oa at Car). queen's’ at (3,0 and queen 'y’ at ad owt s corwrrme | “The above one is the Sowtion for 4 -queen problem. | 2 Ba as oy | Pt 1 4 2 a 3 | ata xe + Byax2 + UG xBKM) = BG > [ie in & (|64) g GY BR AVA 1 \%X \* @ \N bd hs 86 oH O | ?@ | al W Pal * 5 © OOO OF Fee owanryation of aH ates. k ve of the u-quee i | "| : ns Solution spate. No | numbered as 1D Clepth Fixst search , “ Ls a queens pobler also Same os above queens problem: Guin 0 subsets gsvblem’- ns numbers called walq nts and we have © we Ore geen Ip poctive m. this find all combinations of these numbers who sum 3 is called Sur lem - Example for 5ay $3, $4 950561 $5) 10 Lad 1 197808 m= 2 $6 os 8h= . . ; 5, 10118 = 20 [ ile golubions | Gap toh = 20 constraint The sum af the ahaa gelected solutions shoutd not euceed “the value of ‘at oy not fnetuced - 2 TH this problem: he solutions MAY (om) ™Lime. complerity :2™ | enple:- | From example’ fi $a/84,5H-85:564 oF Bio tay B15) A038 12 3 4 ® , 1 0? | subset = $1a5U- ord sowwtion!— I= fio,aoy. forsardarstsss.Sey D {5,lrlar 115 .a0%oe poe ee ee ee | i Geragh _colouving Graph coltusting is Q pwbler of. cauing each vertex t a qrath fn a such a way thet no two adjacent vertices have Same colour and ™ colours ave used 40 louy the vewtices- Therefore this poblem fs also called as M™ colouring problem - constiaint No two adjacent vertices and nelq greasing ventiees chould not be coloured with same colour. | Fkample— Hence we vequhe 3 coloUxs tp colous+the graph, then the chapmatic number of given graph (3 8- We Use: back -racking technique +0 Solve -this prblem - consider the graph: Dgraph gq constels of vertices nn) aa) Rae D there ove 3 colours used reds green and Wues te cuit numiey them out as j—veds a-green » 3—blue te me Cannge astgn the colour cithey 4 oy 2 ors for c’ becuse the graph catouring papblem constraint #8 that ho Ewe adjacent vestees have the Same colour y? IF we assign colour 4 to © then adjacent vertex ofc tbe A is having colour: 4. sinflanly g 7s having 2 and having 3:| therefore we reed 0 bacetrack1Ng \ | oO | -ime complevity - U (c") Ly 6 Tete no: % COONS using ™ Hamiltonian cyele- consider any starting vertex & travelling froma starting Vortex visiting evey node atleast once and ot last tHavelling back to the ‘it forme a cycle and this cqele formed #8 Known as Hamiltonian dle startin vertex, then Lo) -Hamtitonian path (of) -HamiHonton graph: |? Back-rocking method is wed In his problem +o find ou the mut ple Solutions | posstble solutions: ni NN: of vertices | €xample > | \ a . yam above example , n=b hence there will be 6! ie. 420 possible Sowtions Time complexity - o(n)) where nts no: of veatices.