We consider the problem of private approximate nearest neighbor (ANN) search. A user seeks the closest vector to a target query $q$ among $M$ vectors stored in a system of $N$ non-colluding databases. The user aims to retrieve the ANN without revealing information about $q$ to any of the $N$ databases. We provide an information-theoretic formulation of the problem and propose an achievable scheme based on a tree-structured ANN search mechanism. The proposed scheme uses a coding-theoretic approach to traverse the branch in the tree structure that leads to the approximately closest vector to $q$ while guaranteeing perfect information-theoretic privacy. We prove that our approach achieves a communication cost of $O(N^2M^\frac{1}{N-1})$ for $N$ databases. For large $M$, this communication cost is lower than competing cryptographic ANN search protocols.