We define and study the decision problem of the emptiness of an attack tree. This decision problem reflects the natural question of knowing whether some attack scenario described by the tree holds in a given model of the system to defend. We establish accurate complexity bounds, ranging from NP-completeness for arbitrary trees down to NLOGSPACE-completeness for trees with no occurrence of the AND operator. Additionally, if the input system to defend has a succinct description, we show that the emptiness problem is PSPACE-complete.