# Algorithms | Misc | Question 16

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is: (GATE CS 2005)**(A)** nk**(B)** (n – 1) k+ 1**(C)** n( k – 1) + 1**(D)** n( k – 1)**Answer:** **(C)****Explanation:** For an k-ary tree where each node has k children or no children, following relation holds

L = (k-1)*n + 1

Where L is the number of leaf nodes and n is the number of internal nodes.

Let us see following for example

o / | \ o o o / | \ / | \ o o o o o o / | \ o o o k = 3 Number of internal nodes n = 4 Number of leaf nodes = (k-1)*n + 1 = (3-1)*4 + 1 = 9