As a point of reference, it is good to know that MNIST (handwritten digits) can be solved extremely well with nearest-neighbour classifier, see: http://yann.lecun.com/exdb/mnist/

It should be not surprising that strategies "memorize all input and interpolate between" are powerful, no matter if as a part of neural networks or other easy-to-overfit techniques (such as random forest).