We examine the appearance of power-law behavior in rooted tree graphs in the context of river networks. It has long been observed that the tails of statistical distributions of upstream areas in river networks, measured above every link, obey a power-law relationship over a range of scales. We examine this behavior by considering a subset of all links, defined as those links which drain complete Strahler basins, where the Strahler order defines a discrete measure of scale, for self-similar networks with both deterministic and random topologies. We find an excellent power-law structure in the tail probabilities for complete Strahler basin areas, over many ranges of scale. We show analytically that the tail probabilities converge to a power law under the assumptions of (1) simple scaling of the distributions of complete Strahler basin areas and (2) application of Horton's law of stream numbers. The convergence to a power law does not occur for all underlying distributions, but for a large class of statistical distributions which have specific limiting properties. For example, underlying distributions which are exponential and gamma distributed, while not power-law scaling, produce power laws in the tail probabilities when rescaled and sampled according to Horton's law of stream numbers. The power-law exponent is given by the expression phi=ln(R(b))/ln(R(A)), where R(b) is the bifurcation ratio and R(A) is the Horton area ratio. It is commonly observed that R(b) approximately equal R(A) in many river basins, implying that the tail probability exponent for complete Strahler basins is close to 1.0.