  A fringe subtree of a rooted tree is a subtree consisting of one of the nodes
and all its descendants. In this paper, we are specifically interested in the
number of non-isomorphic trees that appear in the collection of all fringe
subtrees of a binary tree. This number is analysed under two different random
models: uniformly random binary trees and random binary search trees.
  In the case of uniformly random binary trees, we show that the number of
non-isomorphic fringe subtrees lies between $c_1n/\sqrt{\ln n}(1+o(1))$ and
$c_2n/\sqrt{\ln n}(1+o(1))$ for two constants $c_1 \approx 1.0591261434$ and
$c_2 \approx 1.0761505454$, both in expectation and with high probability,
where $n$ denotes the size (number of leaves) of the uniformly random binary
tree. A similar result is proven for random binary search trees, but the order
of magnitude is $n/\ln n$ in this case.
  Our proof technique can also be used to strengthen known results on the
number of distinct fringe subtrees (distinct in the sense of ordered trees).
This quantity is of the same order of magnitude in both cases, but with
slightly different constants in the upper and lower bounds.
