Tree descent
A binary tree contains nodes, and each node has an odd number of descendents . What is the number of nodes in that tree that contain exactly one child?
Details and Assumptions
-Every node it its own descendent.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
\text{Let \$d\_u\$ the number of descendents of \$u\$, then:} \\ \text{\$d\_u=1+d\_{l\_u}+d_{r_u}\$ where \$l_u, r_u\$ are children of \$u\$.} \\ \text{Suppose wlog that \$u\$ has only \$l\_u\$, then} \\ \text{\$d\_u=1+d\_{l\_u}\$} \\ \text{But \$d\_{l\_u}\$ is odd by hypothesis and then \$d_u\$ must be even, contradiction!}