binary tree data structures

Can anybody give me proof how the number of nodes in stri开发者_运维技巧ctly binary tree is 2n-1 where n is the number of leaf nodes??

Proof by induction. Base case is when you have one leaf. Suppose it is true for k leaves. Then you should proove for k+1. So you get the new node, his parent and his other leaf (by definition of strict binary tree). The rest leaves are k-1 and then you can use the induction hypothesis. So the actual number of nodes are 2*(k-1) + 3 = 2k+1 == 2*(k+1)-1.

just go with the basics, assuming there are x nodes in total, then we have n nodes with degree 1(leaves), 1 with degree 2(the root) and x-n-1 with degree 3(the inner nodes) as a tree with x nodes will have x-1 edges. so summing

n + 3*(x-n-1) + 2 = 2(x-1) (equating the total degrees)

solving for x we get x = 2n-1

I'm guessing that what you really want is something like a proof that the depth is log₂(N), where N is the number of nodes. In this case, the answer is fairly simple: for any given depth D, the number of nodes is 2^D.

Edit: in response to edited question: the same fact pretty much applies. Since the number of nodes at any depth is 2^D, the number of nodes further up the tree is 2^D-1 + 2^D-2 + ...2⁰ = 2^D-1. Therefore, the total number of nodes in a balanced binary tree is 2^D + 2^D-1. If you set n = 2^D, you've gone the full circle back to the original equation.

I think you are trying to work out a proof for: N = 2L - 1 where L is the number of leaf nodes and N is the total number of nodes in a binary tree.

For this formula to hold you need to put a few restrictions on how the binary tree is constructed. Each node is either a leaf, which means it has no children, or it is an internal node. Internal nodes have 3 possible configurations:

• 2 child nodes
• 1 child and 1 internal node
• 2 internal nodes

All three configurations imply that an internal node connects to two other nodes. This explicitly rules out the situation where node connects to a single child as in:

   o
  /
 o

Informal Proof

Start with a minimal tree of 1 leaf: L = 1, N = 1 substitute into N = 2L - 1 and the see that the formula holds true (1 = 1, so far so good).

Now add another minimal chunk to the tree. To do that you need to add another two nodes and tree looks like:

    o
   / \
  o  o

Notice that you must add nodes in pairs to satisfy the restriction stated earlier. Adding a pair of nodes always adds one leaf (two new leaf nodes, but you loose one as it becomes an internal node). Node growth progresses as the series: 1, 3, 5, 7, 9... but leaf growth is: 1, 2, 3, 4, 5... That is why the formula N = 2L - 1 holds for this type of tree.

You might use mathematical induction to construct a formal proof, but this works find for me.

Proof by mathematical induction:

The statement that there are (2n-1) of nodes in a strictly binary tree with n leaf nodes is true for n=1. { tree with only one node i.e root node }

let us assume that the statement is true for tree with n-1 leaf nodes. Thus the tree has 2(n-1)-1 = 2n-3 nodes

to form a tree with n leaf nodes we need to add 2 child nodes to any of the leaf nodes in the above tree. Thus the total number of nodes = 2n-3+2 = 2n-1.

hence, proved

To prove: A strictly binary tree with n leaves contains 2n-1 nodes.
Show P(1): A strictly binary tree with 1 leaf contains 2(1)-1 = 1 node.
Show P(2): A strictly binary tree with 2 leaves contains 2(2)-1 = 3 nodes.
Show P(3): A strictly binary tree with 3 leaves contains 2(3)-1 = 5 nodes.
Assume P(K): A strictly binary tree with K leaves contains 2K-1 nodes.
Prove P(K+1): A strictly binary tree with K+1 leaves contains 2(K+1)-1 nodes.
2(K+1)-1 = 2K+2-1
         = 2K+1
         = 2K-1 +2*
* This result indicates that, for each leaf that is added, another node must be added to the father of the leaf , in order for it to continue to be a strictly binary tree. So, for every additional leaf, a total of two nodes must be added, as expected.

int N = 1000; insert here the value of N
int sum = 0; // the number of total nodes
int currFactor = 1; 
for (int i = 0; i< log(N);  ++i) //the is log(N) levels
{
   sum += currFactor;
   currFactor *= 2; //in each level the number of node is double than the upper level
}

if(sum == 2*N - 1)
{
    cout<<"wow that the number of nodes is 2*N-1";
}