Implementation of binary tree

The following text is snippet from algorithms book.

We could draw the binary trees using rectangular boxes that are customary for linked lists, but trees are generally drawn as circles connected by line开发者_运维百科s because they are actually graphs. We also do not explicitly draw NULL links when referring to trees because every binary tree with N nodes would require N+1 NULL links.

My question is what does author mean every binary tree with N nodes would require N+1 null links? how author came with N+1 number?

If you have a tree of 1 node, there are 2 null links (left and right on the root). If you add a node to either left or right, you have filled 1 null and added 2 more. This continues on ad infinitum, therefore for each node added you net 1 extra null leaf.

You could prove this by mathematical induction.

Base case

1 node has 2 NULL links - satisfies the property.

Inductive step

Now assume that all trees with n-1 nodes have n NULL links. Then we wish to show, that all trees with n nodes have n+1 NULL links.

Take any tree with n nodes, and pick one of the leaves. Remove this leaf. We now have a tree with n NULL links, per our assumption. If we add the leaf again, we lose one NULL link, but gain two. Thus, we have n - 1 + 2 = n+1 NULL links on the tree with n nodes.

Observation: Each edge acts as a link. N-1 edges for N nodes.

Totally links: 2N.

Null links: 2N - (N-1) = N+1.