3 votes 3 votes Consider a binary tree T that has 150 leaf nodes. Then the number of TOTAL nodes in T that have exactly two children are ______. DS data-structures tree binary-tree + – iarnav asked Jan 7, 2018 iarnav 971 views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply Raju Kalagoni commented Jan 7, 2018 reply Follow Share 149! 1 votes 1 votes Shubhanshu commented Jan 7, 2018 reply Follow Share 149 Total number of the Internal nodes which is having exactly two children. And there are total 299 nodes. 1 votes 1 votes Ashwin Kulkarni commented Jan 7, 2018 reply Follow Share In Binary tree, It is easy by just observing, But for n-ary tree try to apply this logic, 1 Internal node = n children 2 internal nodes = n - 1 children + n children [why this, because out of above n leaves we are making one non leaf, then again n children for that non leaf] 3 internal nodes = (2n -1) -1 + n = 3n -2 children So pattern is X non leaves = Xn - (X-1) leafs now in our case Xn - (X-1) = 150 Hence X = 149. In binary tree it is easy to solve by observing 2-3 small trees, leaf - 1= internal. But hope this helps for complex trees. :) 1 votes 1 votes Ashwani Kumar 2 commented Jan 7, 2018 reply Follow Share All the internal nodes in Binary tree have exactly 2 childrens Let $N$ be total no of nodes, $I$ be total internal nodes and $L$ are no of leaves Binary tree then $N=2*I+1$ Also $N=I+L$ $I+L=2*I+1$ $I=L-1$ Given $ L=150$, $I=150-1=149$ 0 votes 0 votes sourav. commented Jan 7, 2018 reply Follow Share https://gateoverflow.in/2604/gate1995_1-17 @Ashwani : it is no where given that All the internal nodes in Binary tree have exactly 2 childrens So your formula $N=2 \times I +1$may not hold always true . 0 votes 0 votes Ashwani Kumar 2 commented Jan 7, 2018 reply Follow Share @sourav It should be "Total no of nodes in m-ary tree is, $ n = m*i + 1$" , right? 0 votes 0 votes sourav. commented Jan 7, 2018 reply Follow Share @ashwani your formula will hold iff every node have either $0$ children or $m$ children ..you can try to take $m=2$ and include one node having $1$ child and then calculate $n$ , you will get incorrect result . 1 votes 1 votes Ashwani Kumar 2 commented Jan 7, 2018 reply Follow Share @Sourav Yes that I know, I got that it is true for complete Binary tree but it also not given that it is complete or every internal node have 0 or 2 children. Correct way to do this: # of nodes with 0 children (leaves) = 150 # of nodes with 1 children = p # of nodes with 2 children = q Total nodes = 150+p+q total edges = 149+p+q 2* total edges = Sum of degree 2*(149+p+q) = 150*1+p*2+q*3 -1 On solving q = 149 2 votes 2 votes sourav. commented Jan 7, 2018 reply Follow Share yes now its correct 1 votes 1 votes smsubham commented Feb 17, 2018 reply Follow Share https://gateoverflow.in/2604/gate1995_1-17 0 votes 0 votes Diksha kiran commented Apr 11, 2020 reply Follow Share Thanks 0 votes 0 votes Hira Thakur commented Oct 10, 2023 reply Follow Share gate-cse-2015-set-3 gate-cse-2015-set-2 0 votes 0 votes Please log in or register to add a comment.