In the field of Automatic Programming (AP), the solution of a problem is a program, which is usually presented by a tree with a specific structure. This tree contains different types of nodes, and is called an AP tree. For solving AP problems, we propose a new local search procedure that adapts the known `elementary tree transformation' (ETT) into this specific tree. Our results indicate that the neighborhood size of an AP tree is for the order of magnitude smaller than the neighborhood size of a tree with one type of node. As our new ETT local search can be part of many meta-heuristics, it can be used to solve various AP problems. In this paper, we incorporate it into the Basic variable neighborhood programming (BVNP) scheme to solve the Symbolic regression problem. Computational experiments were conducted to test the performance of our proposed method; it was compared with the three well known automatic programming methods, i.e., the VNP method without ETT, Genetic programming, and Artificial bee colony programming. The obtained results show clearly the greater ability of our method, with respect to convergence speed and computational stability.