What makes a Tree-Structured Parzen Estimator "tree-structured?"
It means that your hyperparameter space is tree-like: the value chosen for one hyperparameter determines what hyperparameter will be chosen next and what values are available for it.

From a HyperOpt example, in which the model type is chosen first, and depending on that different hyperparameters are available:

space = hp.choice('classifier_type', [
{
    'type': 'naive_bayes',
},
{
    'type': 'svm',
    'C': hp.lognormal('svm_C', 0, 1),
    'kernel': hp.choice('svm_kernel', [
        {'ktype': 'linear'},
        {'ktype': 'RBF', 'width': hp.lognormal('svm_rbf_width', 0, 1)},
        ]),
},
{
    'type': 'dtree',
    'criterion': hp.choice('dtree_criterion', ['gini', 'entropy']),
    'max_depth': hp.choice('dtree_max_depth',
        [None, hp.qlognormal('dtree_max_depth_int', 3, 1, 1)]),
    'min_samples_split': hp.qlognormal('dtree_min_samples_split', 2, 1, 1),
},
])


From the original paper:


  In this work we restrict ourselves to tree-structured configuration spaces. Configuration spaces are tree-structured in the sense that some leaf variables (e.g. the number of hidden
  units in the 2nd layer of a DBN) are only well-defined when node variables (e.g. a discrete choice of how many layers to use) take particular values.