The tangent number T_{2n+1} is equal to the number of increasing labelled complete binary trees with 2n + 1 vertices. This combinatorial interpretation immediately proves that T_{2n+1} is divisible by 2^n. However, a stronger divisibility property is known in the studies of Bernoulli and Genocchi numbers, namely, the divisibility of (n + 1)T_{2n+1} by 2^(2n). The traditional proofs of this fact need significant calculations. In the present paper, we provide a combinatorial proof of the latter divisibility by using the hook length formula for trees. Furthermore, our method is extended to k-ary trees, leading to a new generalization of the Genocchi numbers.