  The primary problem in property testing is to decide whether a given function
satisfies a certain property, or is far from any function satisfying it. This
crucially requires a notion of distance between functions. The most prevalent
notion is the Hamming distance over the {\em uniform} distribution on the
domain. This restriction to uniformity is more a matter of convenience than of
necessity, and it is important to investigate distances induced by more general
distributions.
  In this paper, we make significant strides in this direction. We give simple
and optimal testers for {\em bounded derivative properties} over {\em arbitrary
product distributions}. Bounded derivative properties include fundamental
properties such as monotonicity and Lipschitz continuity. Our results subsume
almost all known results (upper and lower bounds) on monotonicity and Lipschitz
testing.
  We prove an intimate connection between bounded derivative property testing
and binary search trees (BSTs). We exhibit a tester whose query complexity is
the sum of expected depths of optimal BSTs for each marginal. Furthermore, we
show this sum-of-depths is also a lower bound. A fundamental technical
contribution of this work is an {\em optimal dimension reduction theorem} for
all bounded derivative properties, which relates the distance of a function
from the property to the distance of restrictions of the function to random
lines. Such a theorem has been elusive even for monotonicity for the past 15
years, and our theorem is an exponential improvement to the previous best known
result.
