  Tree size ($\rm{TS}$) is an interesting measure of complexity for multiqubit
states: not only is it in principle computable, but one can obtain lower bounds
for it. In this way, it has been possible to identify families of states whose
complexity scales superpolynomially in the number of qubits. With the goal of
progressing in the systematic study of the mathematical property of $\rm{TS}$,
in this work we characterize the tree size of pure states for the case where
the number of qubits is small, namely, 3 or 4. The study of three qubits does
not hold great surprises, insofar as the structure of entanglement is rather
simple; the maximal $\rm{TS}$ is found to be 8, reached for instance by the
$|\rm{W}\rangle$ state. The study of four qubits yields several insights: in
particular, the most economic description of a state is found not to be
recursive. The maximal $\rm{TS}$ is found to be 16, reached for instance by a
state called $|\Psi^{(4)}\rangle$ which was already discussed in the context of
four-photon down-conversion experiments. We also find that the states with
maximal tree size form a set of zero measure: a smoothed version of tree size
over a neighborhood of a state ($\epsilon-\rm{TS}$) reduces the maximal values
to 6 and 14, respectively. Finally, we introduce a notion of tree size for
mixed states and discuss it for a one-parameter family of states.
