CODEWITHSUNDEEP
algorithmproof
venkysmarty
venkysmarty

Reputation: 11441

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 lines 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?

Upvotes: 4

Views: 1573

Answers (3)

RobinSun
RobinSun

Reputation: 11

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

Totally links: 2N.

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

Upvotes: 1

Sebastian Paaske Tørholm
Sebastian Paaske Tørholm

Reputation: 50948

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.

Upvotes: 4

Nick Larsen
Nick Larsen

Reputation: 18877

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.

Upvotes: 7

Related Questions