The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 votes

In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is:

  1. $nk$
  2. $(n-1)k + 1$
  3. $n(k-1) +1$
  4. $n(k-1)$
asked in DS by Veteran (67.7k points)
edited by | 1.4k views

Before looking at answer just  form following two equation and try to solve -->

  1. Equation for total degree.
  2. Equation for total node.

5 Answers

+9 votes
Best answer
Answer :-> C)n(k-1) +1

Originally when we have root , there is only 1 node, which is leaf.(There is no internal node.) From that "+1" part of formula comes from this base case.

When we k children to nodes, we make root internal. So then Total Leaves = n(k-1) + 1 = (k-1) + 1 = k

In k complete k ary tree every time you add k children , you add k-1 leaves.( +k for leaves, -1 for node which you are attaching )
answered by Veteran (46.8k points)
selected by
+7 votes
total nodes=nk+1(1 for root)

leaves =total nodes -internal nodes


answered by Veteran (33.3k points)
here k is not internal node ..... n is internal node and

leaves node = internal node (k-1)+1

leaves= n(k-1)+1

and total nodes = n(k-1)+1+n= nk+1

so ans should be (c)

It was typo thanks for correcting...


+3 votes
Option c.
answered by Loyal (3.2k points)
+2 votes

leaves node = internal node (k-1)+1

leaves= n(k-1)+1

and total nodes = n(k-1)+1+n= nk+1

so ans should be (c)
answered by Veteran (13.6k points)
+1 vote
#leaves * degree_of_each_leave + #internal_nodes(excluding the root) *degree_of_each_internal node + degree of root=2(number of edges)

number of leaf node is( say l)

here degree of leaf node is 1

number o internal nodes(excluding root)is n-1

degree of each internal node is k+1

degree of root is k

number of edges=l+n-1




answered by Veteran (13.6k points)

more precisely just solve this two equation to get answer of any such ques!



where  N=number of nodes i=no of internal node k= k-ary l=leaves
in some que root node is not consider as internal node but in thi que root node is consider as internal node..why ??

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,157 questions
36,984 answers
34,823 users