Explain in detail that if m pointer fields are set aside in

Explain in detail that if m pointer fields are set aside in each node of a general m-ary tree to point to a maximum of m child nodes, and if the number of nodes in the tree is n, the number of null child pointer fields is n*(m-1)+1.

Solution

M-ary tree have m pointer fields for each node (MN pointers). There are N-1 edges in a m-ary tree, so that the number of null child pointer fields is,

MN - (N-1) = MN - N + 1 = N(m-1) + 1

The null pointer theorem states that the number of nodes m of a regular m-ary tree are related to the number of null pointers P and is given by,

P = (n-1) (m+1)

Proof:

The no. of pointer = m x n. Moreover, the fact that each node is pointed by a pointer in one correspopndence concept. The root node implies a non-null pointers are totally n-1.

Hence, by simple arithmetic: m x n - (n-1) = (m-1) x n + 1

P = (m-1) x n + 1

When m = 2, P = n+1