Tree problem 1

Solution to part (b)

Suppose each internal node in the tree has only a single child. Then the rank of the whole tree will be zero.

If the tree is full and complete, then the rank of the tree will be the same as its height.


More generally, the rank of a tree measures the height of a full and complete tree that is (informally) buried inside your tree. You can find this full and complete tree by getting rid of nodes that don't branch by merging them with their (single) child.