0 votes 0 votes Leaf Nodes =[ Internal nodes with degree 2 ] + 1 It is valid if we consider Tree as undirected graph ? Or is it valid only for Tree when considered as directed graph DS programming-in-c tree + – jatin khachane 1 asked Dec 29, 2018 • edited Dec 29, 2018 by jatin khachane 1 jatin khachane 1 767 views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply Lakshman Bhaiya commented Dec 29, 2018 reply Follow Share what is the meaning of a directed tree and undirected tree? 0 votes 0 votes jatin khachane 1 commented Dec 29, 2018 reply Follow Share https://gateoverflow.in/3548/gate2006-it-9?show=38353#c38353 0 votes 0 votes Lakshman Bhaiya commented Dec 29, 2018 reply Follow Share @jatin khachane 1 see my comment what I ask to you, please defined both terms? 0 votes 0 votes jatin khachane 1 commented Dec 29, 2018 reply Follow Share Actually I mean to say Tree as directed graph and Tree as undirected graph 0 votes 0 votes Lakshman Bhaiya commented Dec 29, 2018 reply Follow Share tree and graph both are same? 0 votes 0 votes Lakshman Bhaiya commented Dec 29, 2018 reply Follow Share in question it is not clear? 0 votes 0 votes jatin khachane 1 commented Dec 29, 2018 reply Follow Share See this 0 votes 0 votes MiNiPanda commented Dec 29, 2018 i edited by MiNiPanda Dec 29, 2018 reply Follow Share @Lakshman Patel RJIT He meant that is that formula true when take tree as directed graph or undirected graph. @jatin khachane 1 Tree by default is a directed graph so minimum degree is 0 i.e. deg of leaf. But if we treat in as undirected graph then min deg becomes 1. But the above formula holds for tree as directed graph. leaf nodes = internal nodes+1 (for full binary tree) leaf node=internal nodes with deg2 + 1 (for all trees) 2 votes 2 votes Shaik Masthan commented Dec 29, 2018 reply Follow Share @jatin khachane 1 i suggest you to " Don't remember the formulas, derive them whenever those are required " it may help you https://gateoverflow.in/8059/gate2015-2-10?show=283868#c283868 0 votes 0 votes jatin khachane 1 commented Dec 29, 2018 reply Follow Share Thnaks bro @MiNiPanda Answer m expecting One more doubt In undirected : A graph is TREE IFF It is connected and has n-1 edges But this may not be true in directed case right 0 votes 0 votes jatin khachane 1 commented Dec 29, 2018 reply Follow Share @Shaik Masthan I didn't remember it ..i found it one answer ..so i found it may not work for directed case so I put question 0 votes 0 votes Shaik Masthan commented Dec 29, 2018 reply Follow Share you didn't provide any explanation of your approach then how can i think you are not remembering it ? Anyway it's upto you :) No need of any further discussions. 0 votes 0 votes MiNiPanda commented Dec 29, 2018 reply Follow Share @jatin khachane 1 But this may not be true in directed case right Why so..? 0 votes 0 votes jatin khachane 1 commented Dec 29, 2018 reply Follow Share In directed Case : degrees possible 0,1,2 Let I = nodes with degree 2 L = nodes with degree 0 X = nodes with degree 1 Sum of degrees = Number of edges [since directed] I(2) + L(0) + X(1) = [I+L+X] - 1 2I + X = I + L + X -1 I = L - 1 ==> L = I +1 @Shaik Masthan Please correct if wrong :( 0 votes 0 votes MiNiPanda commented Dec 29, 2018 reply Follow Share @jatin khachane 1 Yes you are right.. And please check the edit i did in my comment..i misread your question at that time.. 0 votes 0 votes Please log in or register to add a comment.