CODEWITHSUNDEEP
binary-tree
user5361938
user5361938

Reputation:

How to prove full nodes = leaves -1 for a binary tree?

Without a proper mathematical proof how am I supposed to go about proving the number of full nodes (a node which consists of two children (left and right)) is the same number of leaves - 1? A hint was supposed to be using a proof of 'structural induction', unfortunately I do not understand what this means, could anyone help me out here?

Upvotes: 0

Views: 484

Answers (1)

Beta
Beta

Reputation: 99094

Mathematically, proof by induction is a way to prove that a statement S is true for all values of natural number n. The idea is to prove 1) that S(1) is true, 2) that if S(n) is true then S(n+1) is also true, and therefore 3) S(N) is true for all n.

In your case, you want to prove that all binary trees have a certain property. The trick is to show that any binary tree (other than the smallest possible one) can be transformed into a smaller binary tree, such that if the smaller tree has that property, then so does the larger one. Then if you can prove that the smallest possible binary tree has the property, so do all binary trees.

So if you're give a large binary tree, what's the simplest possible way to make it smaller?

EDIT: I suggest you take pencil and paper and try to draw a tree that doesn't have that property. Start with a single node, the root node, and add nodes one at a time, keeping track of the number of full nodes and the number of leaves. Once you are convinced that you can never draw such a tree, read this Answer again and see if it makes sense.

Upvotes: 1

Related Questions