Question

How many null links does an arbitrary binary tree with $n$ nodes have?

• A. $n+1$
• B. $2n$
• C. $2n-1$
• D. $n-1$

Hint:

Always remember: a tree with $n$ nodes has $n-1$ edges. In a binary tree, subtract these from the total $2n$ child pointers to find the number of null links.

Answer 1

The Correct Option is A

Step 1: Define null(n) as the number of null child pointers in a binary tree with n nodes, and treat an empty tree (0 nodes) as having exactly 1 null pointer (the single "no tree here" pointer pointing to it), so null(0) = 1.
Step 2: For a tree with n nodes whose root has a left subtree of L nodes and right subtree of R nodes (with L + R + 1 = n), the total null pointers equal those contributed by the left subtree plus those from the right subtree: null(n) = null(L) + null(R).
Step 3: By induction, since null(0) = 1 and null(n) = null(L) + null(R) with L + R = n - 1, this recursive relation is satisfied by null(n) = n + 1 for every tree shape, regardless of how nodes are distributed between left and right subtrees.
\[ \boxed{\text{null links} = n+1} \]

Answer 2

A third way to establish this is by induction on the number of nodes, tracking how the null-link count changes each time exactly one new node is added to the tree.

Base case: An empty tree (n=0) has exactly one null link overall — the single null pointer representing "no tree here" — giving 0+1=1, consistent with the formula n+1.

Inductive step: Suppose a tree with k nodes has k+1 null links (the inductive hypothesis). Adding one new node to this tree means attaching it in place of one of the existing null links (making that slot non-null now, a change of -1 null link), while the newly added node itself contributes 2 brand-new null child pointers of its own (a change of +2 null links). The net change is -1+2=+1 null link overall.

1. n+1: Starting from the base case of 1 null link at n=0 and adding exactly 1 null link every time a node is added, after n insertions the count becomes 1+n, matching this option exactly at every step of the induction.
2. 2n: This would require the null-link count to grow by 2 for every node added, but the inductive step above shows the net change per node is only +1, not +2, so this option does not match the induction.
3. 2n-1: Checking the base case n=0 gives -1, which is not a valid (negative) null-link count, so this option is inconsistent with the induction's base case.
4. n-1: Checking the base case n=0 gives -1, again an invalid negative count, so this also fails to match the induction.

Tracking the null-link count node by node from an empty tree confirms it increases by exactly 1 with each new node, reproducing n+1.

Therefore, the correct answer is n+1.