Let f be a Boolean function. For e greater than or equal to 0 let D_e(f) be the minimum depth of a decision tree for f that makes an error for less than or equal to an e fraction of the inputs x in {0,1}^n. We also make an appropriate definition of the approximate certificate complexity of f, C_e(f). In particular, D_0(f) and C_0(f) are the ordinary decision and certificate complexities of f. It is known that D_0(f) is less than or equal to C_0(f)^2. Answering a question of Tardos in 1989, we show that for all e>0 there exists a d' > 0 such that for all 0 less than or equal to d < d', we have