We show that top-down decision tree learning heuristics are amenable to\nhighly efficient learnability estimation: for monotone target functions, the\nerror of the decision tree hypothesis constructed by these heuristics can be\nestimated with polylogarithmically many labeled examples, exponentially smaller\nthan the number necessary to run these heuristics, and indeed, exponentially\nsmaller than information-theoretic minimum required to learn a good decision\ntree. This adds to a small but growing list of fundamental learning algorithms\nthat have been shown to be amenable to learnability estimation.\n En route to this result, we design and analyze sample-efficient minibatch\nversions of top-down decision tree learning heuristics and show that they\nachieve the same provable guarantees as the full-batch versions. We further\ngive "active local" versions of these heuristics: given a test point $x^\\star$,\nwe show how the label $T(x^\\star)$ of the decision tree hypothesis $T$ can be\ncomputed with polylogarithmically many labeled examples, exponentially smaller\nthan the number necessary to learn $T$.\n