Help on computing some property value of a binary tree.

Question

I am trying to compute some properties of a binary tree, but I cant find its formula. What I did to get the initial value is, I draw the binary tree on paper and manually count the nodes, pairs, etc. But I was not able to create formula out of it. The only thing I got is the number of nodes per level.

+-------+-------+----------------------+---------------+-----------------------+
| Index | Level | # of nodes per level | maximum nodes | total leaf nodes pair |
+-------+-------+----------------------+---------------+-----------------------+
|     0 |     1 |                    1 |             1 |                     0 |
|     1 |     2 |                    2 |             3 |                     1 |
|     2 |     3 |                    4 |             7 |                     5 |
|     3 |     4 |                    8 |            15 |                    17 |
|     4 |     5 |                   16 |            31 |                    49 |
|     5 |     6 |                   32 |       unknown |               unknown |
+-------+-------+----------------------+---------------+-----------------------+

The maximum nodes is the overall total count of nodes.

The total leaf nodes pair is the sum of all the node leaf pairs.

For example, the Tree has 3 levels, then the first node on level 1, will got 3 leaf pairs.

Then two nodes on level 2, will get 1 pair each, while 4 nodes on level 3 while got zero pairs each. Then total of it overall is 5.

What would be the formula for computing the maximum nodes and total leaf nodes pair?

EDIT Additional info about the total leaf nodes pair.

(should be a perfect/complete binary tree)

• If a parent node has 3 child node on left and has 3 child node on the right, then its total leaf node is 3.
• Sum all the pairs of every node, then that will be the total leaf nodes pair of the tree.
• Example, lets say we only got 2 levels. The first level will got 1 child on left and 1 child on right, so the very first node will have 1 pair. While the nodes on 2nd level will got none because they are no more nodes below them. Then the total leaf nodes pair will be only 1.
• Another example, lets assume we got 4 levels
  • Because the total level is 4, then the very first node will have 7 pairs. 7 pairs because, on complete binary it will have 7 child nodes in left and right.
  • Then the next 2 nodes on level 2, will got 3 pairs each. 3 pairs each because, on complete binary they will have 3 child nodes in left and right. With the total of 6.
  • While the 4 nodes on level 3, will got 1 pair each. 1 pairs because they only have 1 pairs of child nodes each. With the total of 4.
  • And the last 8 nodes on level 4 will got nothing because they don't have child nodes. zero because, this is the last level and there is no more nodes below.
  • In total, there is 17 total leaf nodes pair

Edit with solution

I tried to solve it by my self and come up with this solution. Pardon I cant be sure if this is the right way to write this solution. $$\sum_{n=1}^{m}\sum_{x=m-1}^0(2^x)(2^{n-1}-1)$$

Request to reopen this question

I got my answer, but @GarethMa solution is much better.

Can I request this question to re-open, so than @GarethMa can post its solution.

P.S.

@GerryMyerson posted link, also solve the second total leaf nodes pair problem, the only difference is it at starting $$index = 0$$ while @GarethMa answer is starting on $$index=1$$

Thank you.

Answer 1

For a $n$ level complete binary tree:

Claim: there are $2^n-1$ nodes

Proof: In the complete binary tree, the root level (level $1$) has only 1 node. Level $2$ will have 2 nodes, each a direct child from the root. Level $3$ will have 4 nodes, each a direct child of the previous level. All the way until level $n$ has $2^{n-1}$ nodes.

Total amount of nodes = $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$

~~

Claim: there are $(n-2)2^{n-1}+1$ leaf nodes pair.

Proof: This time we can work backwards. We can consider each node in each level, and sum up the contribution as following:

$$\textrm{LN Pair} = \sum_{l=1}^n (\textrm{number of nodes in level } n)(\textrm{leaf node pair of node in level } n) = \sum_{l=1}^n (2^{l-1})(f_n(l))$$

Let's look at a numerical example to figure out what $f_n(l)$ is. Let's look at $n=4$, $l=2$. Each node in $l=2$ has 3 children in subtree, and thus $f_n(l)=f_4(2)=3$. It shouldn't be hard to see that $f_n(l)=\textrm{number of nodes in complete binary tree with height } (n-l) = 2^{n-l}-1$

$\therefore$ required sum is $$\sum_{l=1}^n(2^{l-1})(2^{n-l}-1)=\sum_{l=1}^n 2^{n-1}-2^{l-1}=n2^{n-1}-(2^n-1)=(n-2)2^{n-1}+1$$ as desired! :)