UNIT-5 Trees The list, vector, stack and queue ADT!S [ dato. sheuct,, ave encountered go far axe linear: A tree imposes 5 ‘brevaychial:( and thus noo linear) shuctuve on & Celhey., Of ikem A tree data Struchuve ean be defined recursively oy a collection of nodes (claxting al wot node) wheve each, Node is a datostruchure consisting of a value, bog ete with a lisk of weferences fo nodes (the “childven'), sit, the tonetratnks that no sefevence is duplicated and hone Poinks bo the ook Teee Example: yer. ON edge * giblings \ A 4] i | \ yb _/ \ tS et . CEC RG) j Dvon exninalogy and Defrai ion, I oot a bee da the firsl node is called 4% an SAY In ta sbuclure ’ oot node's Every bree must have 4 ssook noder We c *R Hrat the yoot node 15 the cnigin of the beee dota shucliw: my tree, there must be only one wook nodes We never have muliple xoot nodes in a bee. ; (Ay > oot , 2) © / / . ‘ OO® f @ ( . do ©... ~ pexse SA’ is the xsool node | ¢ + |p ang deee the fies node is called oa," ROOT Node “ EDGE In a bree datashuclure the conga fink between any bwo nodes is called os *epge” In a twee with IN’ \n-4! numbex of nodes these will be, a im aninu of nurnbex of edges: pet wn a ‘ iny bree , Edge! is vannedtina fink between two nodes ~~ i oa3: parent In a byee datashuchme the node which is Predeceng, any node isi called, as "PARENT Nope”. In simple We the node, which has a branch From it be any Offre ra 4S called a pavent nodes paxent node Can alco be defi 04 "The node which has child/children! | / X\ Herve As BCE BG 3| io Parent nodes. dood > HOO t In any tree the node which hos chi td/chi Idven vs | Called ‘Pavenl’- * Ar node which is Predecessor of any othey node is calle ‘Pavent!. 4+ child . In a bree datashucure, the node which is “escent oF any node is ¢alled as CHILD Node: tA Sebo words, | the node nibrels has link from ik pasent node is calle As child nodes In a tree Any parent node can have# number of child nodes. In a bree, all the nodes | “except ook are child Nodes. “4 | J® 8 (¢ Hewe GGH ave chide OQ Q®O® (i) stere k ap is child #4 o descendant of ary ™ Cv) (&) 1S called as aon Heve BEC ave childgIBLINEE po a bee dotashuc hive, nodes which belong fo same at axe Called 0% “SIBLINGS” In simple Words, the nodes with Same Pa @) Heve B&c ae siblings | eve DE RF ae siblings AD c mv \ " fewe G RH ave siblings (p) ©) ® a (8) Heve | 81 ave siblings \ e|n any tree the nodes yen ‘dye called * sibling Nodes! | © © hich has Same parent - Ave called “sibli ings" + The childxen of a pasent ave called * siblings" be beat : In a bee ‘dato sbouchure have a ichild is Called as LEAF: Node.» In sirnple a leaf is anode with no child. tn a bree datasbuclure, the leaf nodes ave called as External nodes”. External node is no child. in. a bree, leat node is called 05 @ ), also 4 node with Le Terminal code! + Heve Di ty Fi Kat Ave Leaf nodes: + In any Hee the node ‘e CA) hich does not have childsen is called ‘Leaf! © Go ® op Leaf nodes node without successors in cated a ‘leaf! node.4 a Internal nodes nodes Ina bree os datestnuchore the node wh d as? INTERNAL Node". < a nede with aHeasl one child. sch has @Heag. | one child is calle In sirople why, dn internal node & Ina bree datasbructuve 1 nodes Other than leaf rod, eynal Nodes The voot node is also said ag rove than ne node, ; ave called as Int be Infemal node. lf the tree “h Internal nodes Ave also Called o& "Nom berminal ” Nede,| A) my Here aiBic, E&G Ave Internal nodes. (-) on any tree’ the node 8) stg @ eo which has aHeoyt one child is éalled'Intemal’ oO o @ node + Every non- leaf rode is called as ‘Internal ! node. & DEGREE In. a tree dotasbuchuye , the botal novof children of Anode is called as * DEGREE" of thak nodertn simple words, the degree’ of & node is total number of childsen it hasithe. highest degree of node ameng all the nodes ina tree iS called ag Degree of tree". | @ Rew pejree. of B IS3 | i Ay (tere Negree of A is2 - Herve Degree of £ iSO © / * In any teee ‘Degree? a Oo of nede is total number of childern it Hos.eee | © ip a Wee daxastsuchuve ,the vook, node is Said bo be at evel 0 and the childven of woot node ave ak level 4 and the | bevel 4. will be at level ee each step from top | count starts childven of the nodes hich ave at a goon <= ln Simple, words, in a be lp boltorn is called as a bevel and the beve with ‘ol and, incvemented by one at each level (ste). i aa a Levele.,.| (a) p revel 7 j i sé - Level 2 2 Level 3 | low Hesght / ; total numbes of edges In a bee "ieee, bel from leaf node b a particular node in the longest path is | height oF the Called as HEIGHT of- that node: f voot node is ‘gaid b be height oF the free « oa tree, | ol. pa ecd In a twee, heght of all lear nodes is et Hoght bs : | eve Height of Hee 53 on any bree, tHeight oP No! . is total no-of edgesfrom | \ Jeak be thet node in SM. honger path: ® Heh! iso * In any bree, Height of, bree! Is the hesght of the ook node-eee 16 a bee data structure, the total number of edger fy Fool rede Io a ‘particular node: is called "AS PEP TH, oF thas | Hodes In a Laee, the fetal ndmbes of edges From root nod, le leaf node in the longest path is Said bo be Depth ef ty In simple words, he highest depth oF any leap node ina lice is aid bo be depth of that tree: In a bree, the depth of yoot node is Lol On peas Here Heaght of be peg? 4 3 ® > ou any bree ‘Height of Nodet is total no-of Bday 6) bOé } From leaf fo that-nod: in longest path rs 2) & yy Heat is © . q "In any Hes, ' Height of tree! 1% the hehe of--wook Node. 18) PATH . In a beee datashruchive, the giaseaue of. ‘nodes! and Edges Koen bre node to ncther node is. cated a ‘path’ belween ak bs eae, § Length or a pe is total rot nodes in that Path-dn below example the Path A~ B-e4 “has length “4 Hexe path beewe? ay) is A-B-E-J Hreve ‘path! beknee? Ny " c&k ig C-G-K “in a teee, ‘path’ is a. Sequence of nodes and edge belween two nodes.‘p) sub PLE "a a hee data shuctuse , each child trom a node fovrs 4 sublet yecursively+ Every child node will be forma eublsee OF its pavent node: & VWF BINARY TREES In a rrosmal freee EVeXy node can, hae 409 qumbex of data struchex childhea» A binary tree & 4 special tyPe of tee in which evesy node can have a maximum op a childven- one | d the othes is known as is known as 4 “lert child” an “Right child”. A tee in which evesy node Gap. have a maximuro ef two childven 6 called “Binaey Tree" - ha binasy tree, every | node can have either Ot ov £ chil Id ot 2 childsen but not more than a Siren.There ave different types ef binary brees. They ave 1 shicky Binary Tree a Full Binayy Tree 3 Extended Binary Tree 4) Complete Bindry Tree In a binasy tree, every node can childyen « Bul in shichty binaxy tree, every node should have exaclty hwo childven or none. Thak means a, Inkemnal node musk have exaclty hwo childven+ A shichy Bindsy Tree Cdn be defined as follows. have maximum of bie | A binary Tree in which evesy node hos eithey brio or Bevo number of childyen is called “ icy Binasy Tree" A ' i eee or ) © ® Dans Di Dab es | : ShicHy Binary bee Yah Sbeucluve “ts ited to epsesent | meestet cal aries LON , : ( + iio 6 ( A+B) #e A+ Bec)3) poll Ginary Tree - is pet In a binary Free, every node can have A maximum of lwo childvens But in sbicly Binayy bee, every node should have exacly two childyen o8 pone And in Full Binary Tree all . nodes mast have exaclty bue childven And at every AD level umber of nodes, level of Full binayy Lyee there must 2 ror example al level a there must be a2. 4 nodes and a sk be 2-8 nodes. internal nede has exch L game level is ab level 3 theve mu A binary fsee in which every hwe childsen and all leaf nodes ave J called “Poll Binasy Tree". 3) Extended Binary Tree Extended Binety NS ; Led into full binary A binary Tree Can be convex nodes when | Tree by adding dummy nodes to existing eves yequived. the full Bindyy Txee obtained by adding dummy nodes to a binary Evee & called os “extended Binary Te 1 | : co Pal 'n above fiquee A nowmal binary bee is converted inte full ee binavy tree by adding durary rode, (bex#) a wlSe ee A céoplele binary Tree is a binary Tree cin Whig every ‘level , except “possibly the last, is Coroplete| Tited’ add a modes as fav leFl as possible, ¢ \, g® xoNL - a Ds A 2) @ UD Xe \F 4 node in a complete binaay bree is assigned a Aumbex K,Where L in(gyA ine) / 4 in(o)B in(F)A Wlaje ° 8 © int) LA 5 5 ini) 0 in) BA ) WG q in(k)cH se . ») @ & JD IDs BFAGECH In adey Lvaversal fo Above example of bindvy bree is {-D-J -B-E-A-@-k-¢-# 7 ight child) 2) pre- Bdex Traversal (woot- lefl-child si ir nee In pre- Sew bsavensal, the rool node ig visited before J sight ebild nedes! ja his traversal, { the left child an the vook node is visited first, then its fresh lert child and lates tks wight child. This pre-Bdew Fewest! is applicable fox evesy woot node of all gubtsee in the tree. step! wisiting the soot node Slepa; visiting a left subtvee slep3; visiting a vight Subbree ge za void presides (6 twee Node * wool) ip Crook L= No-t) printf (° 4d", ool ker) predder ( yoo! > tert child); predides ( wool right child); ay Bs pre(A) = A pse(B) precc) * - ap pecpecPlC \ P prec) pre(H) 2 © @ « | A 7 2 AB D prec) pre) F {t) (5) Ye) | cape CK) H | — ABDI SECaKS, | hak mea hese WE have visited fo ype endes oF A-G- p-I-J3- E-C-G-k- using pre Bder- | the pre didex bsavensal tor above example bindyy tree k-H Os A-B-p- Id FO i post Bidex faaverssal ¢ weptenld-vight child - Root) aoa f node is visited after | dex traversal , the ¥0° | leptchild this travess@ ght child and then fil the Na) posts legtchild and vight child > then its 2 node is visited fixsty sively pexfomed wr ike yok node: This iS yecue: ted. wight most node is visi Alg’ithra; CLR stepi . visiting 4 left subtsee Stepa visiting 4 aight subbee Step3: visiting the wool node: Te y.Void post oxdey (B-Tyee Node # Wook) Poslorder (rool -) lef L-child); Posl des Crool 9 vighl child); PFGs00l | ~ Nutt) Print f(z", yook- ikem) ; \ Exe 7 = A Post (A) > post (B) posk(c) A > Post(o) past (r)B post Ca) posk(H) cA 7 Post) paskG)D FB post Ck) G HER 2 ISDEB KG HCA IFeve we have visited in the Sdey of t-J-D-F-B* -G-H-c-a by using post-@dew Traversal. Post-8des traversal fox above example binary twee is S-Di F_B-K- G-H-c-Acpaph is a non-linear datasbueluve, 1s a collection | “ of nodes ‘and edges in which! nodes having infomation and ‘nodes dye' connected with, edges: Ly ij i t { exaenple so ef ices and she following isa qearh with 5 vertices n 6 edges: » This gysaiph can be defined & - Ge (vi E) i phere v= (A1B/ C101) and / | (AD), (BID), | E= 2 (aig), (AIC), Cer p) (oi Ce} “we use the following datastrucluve fox qpairh | vertex: i | anes | | individual data element of 4 gzaph is called as | vesker. Vester is also known as’ ndde-'In above example | | graph, aiB,c; b, E ave‘ known as vertices: hi We if EDge An edge isa connecting link belween two vertices | Edge is dlgo known as ‘Asc’ An edge is sepvesented os Cslasting yestex, ending vertex) + For example, in. above IL. Qsaph is link between vertices A and B is represented VW| ds(aiB)+ In above example qrarh, theve are 4 ed, ex Cre, CAI): (Arc), (Aid), (B10? CB: 2),'CerP)s (Dre) Edges ave three hyper. \ t undiyected Edge: An undive nal edge lf theve t S undirected edge between veytices A andB then edge (arb) is equal to edge (B,A) Q+ Divected Edge’ A divecled edge is a undiseclional - edge theve *s divected edge B then edge (aiB) is not equal to edge (B/A). 3 Weighted Edge: A weighted edge Ys a edg with value (cost) on ite ; : LA qeaph, with only Dizecked quaph ‘undivecled edges ig Said ty be undiyected geaph- 2 , A graph, with only dise cked edge is Baid to be dixected qearb- Dixed Graph A qsaph, with, both i. undixected and dixected edges ‘aid to be Mixed. quaph. End vertices ov end points ‘The two ‘vewtices « joined by edge ave called end vertices (end,points). of Hrat edge. ipoa edge 's divected, its fivst endpoint is Said to be Gigin of it between Vextices A an cled edge is a bidhec, | |Destinalion . VF edge is disocted , ils hrsl endpoint is Aaid tn he the origin of ib and the other endpoint is Aaid to be * desknabion® of that edge Adjacent If theve is An edge bebween veatices A and B then bol) Aland B ave saidto be adiacent «In othes Was Vestices A and B ase Said bp be addacent if Herve is An edge between them. Incident Edge is Said 4p be incident on a vertex if the Vestex is one of the endpoints of that edge: dubgoing edge . A dinected edge is aid to be outgoing edge on its Bigin vestex. inepning Edge A disected edge is said b be incoming edge on its destination vattex: Total numbex of edges connected b a vertex Is Zaid bo be dequee of that vertex: total purohes, of incoming edges connected bo a vevlex is Said to be iindegree of that vertex:| { - gubdegree Total number: of outgoing edges connected ty vertex is Zoid te be outcleguee of that vertex, pare! edges en nll edges Wf theve ave fwo undiyecked edges with Same end vestices and td divecled edges with, Kame Bigin and destination, Buch edges: ave called parallel edge or Multiple edges. =A cP toep Edge Cundivected oy divected) is @ self loop: if its two eri pinks ceinetde wit each other. Simple Gyerh A graph is Raid bo be Simple if there are no Pavallel and self- loop edges: path A Path is a Sequence of altesnale vertices and edges thot starts abaq “Vertex “and ends with otfex vertex Such that each edge WS ncider to its predecessor and Successor vexlex. G\RAPH IRIEH REPRESENTATIONS lf Adsacency List tr 44 In this wepresentation, every vertex of a qpaPh ‘contains Nisk of phy ihiedconk Vevdices Fo’ example , Bonide the follo wing directed greph sepresertation implemented using Linked list )Gpaph data stucluves ts xepresenled using following gepresentations, _— ) addacency Matix a) Adgacency Lisk adjacency ‘mabria I i ae quorr is sepresented In this -vepresentalion ; the numbex of verlices by 4 using a mabix of size fetal } means a qearh with sige 444 enk vertices Jpfal numbers of vestices «Tha 4 vertices 1s yepsesented using 4 matwia both wows and colurans wepees 4 ov o Hese 4 yepresent to column e From In this atria, This matrix is filled with thok these is an edge tso vertex and o yepuesents in vertex: oo you vertex Rok these 1S no edq wow Vertex to colum undisected epoph ABC DE @— @x aAforrro T | ae) Bjavo ott 5 © cj1 o 01 Of C)——__ ort ryt | Nore Clo 1 2 19 Disected graph : : AB CDE & ON Af o 1 100 AY 5 6] 0 9 Of! POY Be? F Nok i clo o 01° oo 0K “olreo ott Oo tho 9% 99.Adiacency bist In this yepresentation » every veslex of a graph cerloin ist of its adjacent vortices For example, considers the following divecled qrorh yepresentation using Linked list. [ol bs KSA “pis vepwesents Can also be implemented using Aysay as follows - - - Graph Tsavensals Gzoph traversal is a technique used for seaachioy vestex ina gsaph: The qreph braversal is Also used to decide the ovdey of vertices is visited tn the | Search process A qraph bxaversal finds the edges to be used in Zeaach process without creating loops That means Using graph. Lxaversal we visit all the vertices of the graph Without getting into leoping Path: ee|) pes (perth fivst seaxch) 4) BFS (Rreadih fixst seaych) pes Cpepth Fisst Seavch) rs bsavensal of a qreph produces 4 Spanning Ince as final vesule + Spanning bee is a qraph withouk loops We use stack dota shuchuse with maximum gige of total numbew of veslices. in the qvaph to implement DES braversal: we use the following steps bo implement Des bavexsal. she DFS. algglithr works: as Filtowst ! ) We begin by pushing “the! ast value (stavting verter) in Stack: 2) pop element from stack and quist it and push all the adjacency list of vertex fat ts No visited- 3) pepeat step a until all the nodes 0¥ visited ©») stack is empty: Des is defined of we visit all the vexces descend: ants befoxe we move bo an adjacent vestex+ This Concept ts an easy when’ the graph is a true In / the below Fiquee ‘we show the bree “preadey feavensal” processing Requence one of the standand “depth fivst bvavensal”cxrFind owt PES for the following Graph stavling Vertex Is VA’. \ (A <. bby dp ® step i: push the starting . vextex ‘Al, into the Stack. step2! Pop al from stack and, visit the adgacent @y—R oF A fe,X' ts pushed Lint stack: so, pes | _———+-— _—+——T | velal TT Litt blab Steps pop x! Plomn Cae? dnd vieik' th the adjacency Uist of ‘x! ire, *G! ands W! ave eae a the | stack - | ava el ae a * 1 : LG [ He | aa stepas pop'G! andfsom stack and visit, it- adjaceny list Of teluse.p' pushed into the stack. re feldal | TTT bs Lostep © * Pep 'P! from slack and visit t+ The adsacency Mm" hist of ‘pl ike, Vy" pushed into slack. rope ty ~] " PAIX LQTP 1, Lib stack, step 6s Por SH! foom stack and visit ity The adgacency list of *H' fee, “E pushed into the stack. =I ! ale | lel Ds Ltd Le | stack | skep?s pop ‘E! from stack and visit IE ‘The adjacency | isk of SE! ney Y and M, pushed into stack: | . ] | “REMATE LY [stack + a step 3. pop’ M! from stack and Visit it: The Addacency | lisk of ‘mt ive, J! and T is pushed into stack. LJ i 4) os [Ale Jelel lel [| ee | L step 4: pop ‘J’ Fsom stack and msi Ite \ rte. TT. 1. “| | I | pes] Al#\q pin jm) 5 | }-—-L-4j— Step ie; pop ‘y' from Stack and visit ik: v6 DLS lai] oof | “oO “slackBFs (Breadth Fivsk seach) fn BFS Algaithre ofa Lsaversal of a qxaph We sia | AN adjacent vertices before geing b the next level, we fivst saw the BFS Of a bree AS ghown in the below: Algdithm Gy) procedure, oF BFS.,, on j b stept: | steps: Step) + stepa ' steps: select the stavting vertex and push it onh the queue: pop an élemenl from @iueue and visit it ; the ‘adjacency’ list poped élemenbis pushed info the queue: ‘ | Repeat step 2 unlil @ueue is empty ov all the verlices weve visiled J a, ) O é > bb ® push A inky @ueue [ie Pop an'element from opueue dad procers 07 visi ik and alt adjacent fist ive, Bic D Pushed into if queue sf) lel opueur\ aa \ i \ 3: Pop an element from queue ie, B and visit it the adsacency lisk of Big EVF is paced imp Goueue- ars (4s Celnele] | st douewe i p 4: Pop an element from queue Pe € and visit it, theve is no adjacency list of ¢ $0 M0 need 4 push any elements into @ueue Brs steps Pep an element from queue ig, D and visit iF ard an adjacency lick of D he GVH pushed into queue : ; IE and visit 1E skep 6 «/ Pop an elem cerca pues step 9: es ) L and visit ib Step io; Pop an ele eat. from queue 6 step pop an element from Gucve he, F and visib it | ‘BFS racfelele_| fapelsL Jess Sep ai Pop an element from @ucue j-0p @ and visit iE pes Talal clolel lal J rar queue Ie/ Hand visit 1 pop an element from ment fxom queue VSRte ‘Sa BES oF the Graph © | Oh. | 5 {p) -~-@ Step + push starling vertex \A ino queue ‘Cay Boe step2: pop an element from queue tee, A and Visit it rand all adjacency fisk of A fe, x pushed Into QWeue. copter. wt Bla fee ] pep ts fowem step3 pop an element from Queue ree, K Add Visit it and add all adjacency [ist of X fs & G4 ave pushed inky @ueue. fle fan Jom slep4: pop an element Leon @tieue ey and visit tk and add all adjacency list of ‘GQ! he P ave pushed into @oueue. af eg wee ~] aie LAIX 1G | Lele Steps: pop an clined From, Queue: iver H ard vsiF iE and add all adjacency list of H her E pushed ink ‘the @ueue | ! ors AT x |g Tig [Hl we} Preglep 6+ PoP an element from Axieue fe, P ard vsil if *» 7» P and ws ' a — | \? t =) eTefg tude? | TEL le ep 2) Pop an clement from @ueue te E and visit it | and add all adjacency list of E Teer yt “ane Pushed into the queue rlxlelulele | [ely | les steps pop an element from qyeue Ire! mand wet \ it and add all adgacency list op ret | is pushed into the queue | | «la Tale lelay E| Oue - | awe" ue IS ¥ and ly ibe |) stepas Pop an element from uel! TL and =| step tos PoP an element wh queue Fe! visit ik ee (alx[elele. amy] | | oueve