A Theorem about n-ary tree

Definitions:

Pointer

A memory address basically. We can dereference the content of that address to get the information we want.

Node

A piece of memory separated into two areas: the data area and the pointer area. The data area holds the information one would like to store in the memory. The pointer area holds the memory addresses of the other nodes.

Tree

Tree is a data structure in Computer Programming. Tree consists of nodes and and each node points to other nodes or null. Note that, except the root node which is not pointed by any pointer, each node is pointed to by EXACTLY ONE pointer.

Regular tree

A tree which every node contains the same number of pointers. The negation is a irregular tree.

N-ary tree

A regular tree whose nodes contain exactly n pointers.

Root node

This is the special node that points to others but is not pointed to by any one else.

Null Pointer Theorem

The Null Pointer Theorem states that given a regular n-ary tree, the number of nodes m is related to the number of null pointers p in the following way:

Proof

It is obvious that the number of pointers = n×m. Moreover, the fact that each node is pointed to by a pointer in an one-one correspondence except the the root node implies non-null pointers are totally m-1. Hence, by simple arithmetic,

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

Application to the case when n = 2

When n = 2, the tree is called a binary tree. By plugging in n = 2, we find that the number of null pointers and the number of nodes differ only 1! ie.