29 votes 29 votes A complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is given by $x(n-1) +1$ $xn-1$ $xn +1$ $x(n+1)$ DS gate1998 data-structures tree normal + – Kathleen asked Sep 25, 2014 edited Jan 12, 2018 by kenzou Kathleen 14.5k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Neelam_$ingh_222 commented Jul 26, 2020 reply Follow Share easiest way --- no of edges = n*x -------------(1) every internal node contributes n edges no of edges = x+l-1 --------------------(2) since tree with n nodes has n-1 edges equating 1 and 2 n*x=x+l-1 x*(n-1)+1=l where l=leaf nodes x=internal nodes 7 votes 7 votes neel19 commented Feb 1, 2021 reply Follow Share Just draw a binary tree and eliminate the options 0 votes 0 votes Kiyoshi commented Sep 13, 2021 reply Follow Share Similar question : https://gateoverflow.in/1372 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Recursive solution for this problem: $T(x) = T(x-1) + n -1$ $T(0) = 1$ $T(x) = T(x-i) + i \cdot (n-1) $ when i=x, we have x-i = 0 $T(x) = T(0) + x\cdot(n-1)$ $ = 1 + x\cdot (n-1)$ Hence option A Nikhil_dhama answered Feb 5, 2021 Nikhil_dhama comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Let #internal nodes = 1 then #leaves = n #internal nodes = 2 (means one of the leaf out of n leaves become internal node therefore now #leaves=n-1 but cause of adding one more internal node we again got n more leaves therefore #leaves=n-1+n) then #leaves = n-1+n = 2n-1 #internal nodes = 3 then #leaves = 2n-1-1+n = 3n-2 #internal nodes = 4 then #leaves = 3n-2-1+n = 4n-3 : : #internal nodes = x then #leaves = xn-(x-1) = xn-x+1 = x(n-1)+1 Shreya2002 answered Oct 19, 2022 Shreya2002 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Every internal node adds n leaves & subtracts 1 leave expect for the root.Root as an internal node directly add n leaves & a single node is just a 1 leaf. theradash answered Nov 29, 2023 theradash comment Share Follow See all 0 reply Please log in or register to add a comment.