1

Let $T_1$ be a tree of height $h$ such that the root has one child, and the branching factor at each level is one more than the branching factor at the previous level. Thus, the root has one child, that child has two children, each of those children has three children, and so on.

Let $T_2$ be a tree of height $h$ such that the root node has $h$ children, and the branching factor at each level is one less than the branching factor at the previous level. Thus, each of the $h$ children of the root has $h-1$ children, each of those nodes has $h-2$ children, and so on.

Note that in each tree the non-leaf nodes in a level all have the same number of children. Show that the number of nodes in $T_1$ is smaller or equal to the number of nodes in $T_2$.

Brian M. Scott
  • 616,228
John
  • 69
  • You can easily show that $T_1$ has $n!$ nodes at depth $n$ for $n\le h$. In $T_2$ the nodes at depth $h-1$ must have at least one child each, their parents must have at least $2$ children each, and so on, so the root must have $h$ children. From that you can work out the number of nodes of $T_2$ at each depth. Now compare the values for $T_1$ and $T_2$. – Brian M. Scott Jan 02 '16 at 00:51
  • 2
    I really don’t understand why anyone thought this unclear. – Brian M. Scott Jan 02 '16 at 00:56

1 Answers1

1

Hint: Try drawing some small cases (say, up through $h=4$), and look at the number of nodes at each level in each tree. You should be able to see a pattern, understand why the statement is true, and then prove it. (One way to prove it, which shouldn't be hard, is to use the information you develop to actually get an explicit formula for the number of nodes in a tree of each kind of height $h$.)

rogerl
  • 22,399