7
$\begingroup$

For a binary tree what is the number of nodes with two children when the number of leaves is 20?

I know that for complete binary tree, when the number of leaves is x then the number of internal nodes is x-1.

But in the question above the given tree is just the binary tree not the complete binary tree. Also, the number of nodes asked is for those having two children which differs from internal node / non-leaf nodes.

Is there any formula to get this?

$\endgroup$
5
$\begingroup$

Hint:

  • For any tree: $|E| = |V|-1$.
  • For any graph $2|E| = \sum_{v \in V} \deg(v)$.
  • A vertex is a leaf if and only if it's degree is $1$.
  • Except for root, the two-children nodes have degree $3$.
  • Intuition: start with a path (each vertex has degree 2, except for two leaves at the ends); now, each time you change a vertex from degree 2 to degree 3, you have make some other vertex of degree 2 into degree 1, so that the sum of degrees is constant.

I hope this helps $\ddot\smile$

$\endgroup$
5
  • $\begingroup$ I dont think will be able to derive it with the help of any hint, sad am such a dumb :( $\endgroup$ – Maha Feb 9 '15 at 14:03
  • 1
    $\begingroup$ @Mahesha999 You commented "I dont think will be able to derive it with the help of any hint" [emphasis mine]. I'm very sorry to hear that and I admire your honesty. I'm afraid that in such case I am of no help to you. $\endgroup$ – dtldarek Feb 9 '15 at 14:09
  • $\begingroup$ possibly could be the worst comment I put out of frustration $\endgroup$ – Maha Feb 9 '15 at 19:52
  • 1
    $\begingroup$ @Mahesha999 Say, you have a set of numbers $a_1,a_2,a_3,\ldots,a_n$ such that $\sum_k a_k = 2m$. Each of this numbers is either $1$ or $2$ or $3$. Suppose that you start with $$a_1 = 1, a_2 = 2, a_3 = 2, \ldots, a_i = 2, \ldots, a_{n-1}=2, a_n = 1$$ (all equal to $2$ except $a_1$ and $a_n$, so that $m = n-1$) and want to make some of them into $3$'s. Observe that for the sum to be conserved, to change some $a_i$ from $2$ to $3$ you need to also change some other $a_j$ from $2$ to $1$. Can you derive the relation between the count of numbers equal to $3$ and count of numbers equal to $1$? $\endgroup$ – dtldarek Feb 10 '15 at 11:05
  • $\begingroup$ @Mahesha999 Here is a more general formula, but it should also solve your case. $\endgroup$ – dtldarek Feb 10 '15 at 15:15
2
$\begingroup$

Let the number of leaves be $l$. Let the number of nodes with exactly two children be $d_2$ and with exactly one children be $d_1$.

Total degree

$d=l+3d_2+2d_1-1$ (as all nodes with 2 children have degree 3 except the root)

Number of nodes $n=d_2+d_1+l$

Number of edges $e=\frac{d}{2}=\frac{l+3d_2+2d_1-1}{2}$

Number of edges in a tree $e=n-1$

$\therefore \frac{l+3d_2+2d_1-1}{2}=d_2+d_1+l-1$

$\therefore d_2=l-1$

This is the result which I was trying to prove in this question.

$\endgroup$
1
$\begingroup$

The number of leaves minus one is equal to the number of nodes with two children.

Suppose there is a counter-example, then take one with the minimum number of vertices. Take the counter-example tree and remove one of the leaves. There are two things that can happen depending if the leaf is connected to a node that had two or one son. But both give a smaller counter-example as you should check. A contradiction.

$\endgroup$
0
$\begingroup$

The task is to count how many nodes with two children, say n2, and how many leaves n0. So to simplify the problem, we can completely "replace" the nodes with one children with their children. This won't disturb our counting process. Why? Think about it.

                  +----z
                 |
     +----y----+
     |           +----z
x --+
     |           +----z
     +----y----+
                 |
                 +----z

The y's are useless for our problem. x is already qualified for our n2 group (either because of y's are z's, doesn't matter) and the four z's are intact (as leaves) after our "replacement".

Now assume the number of leaves as L. The n2 are just connectors to n0 nodes or connectors to some other nodes in n2. Ask how many are n2 nodes? That's easy. Just add $$ L/2 + L/2^2 + L/2^3+....+L/2^k $$ where L=2^k. Then the The sum is $$ L(1-1/2^k) = L-1 $$

$\endgroup$
0
$\begingroup$

T = L-1
T = node with 2 child,
L = node with 0 child(Leaf nodes).
source: https://www.geeksforgeeks.org/handshaking-lemma-and-interesting-tree-properties/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.