# Data Structures | Binary Trees | Question 15

In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is:**(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.

since its a complete k tree, so every internal node will have K child

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