  In this paper, we study the online nearest neighbor random tree in dimension
$d\in \mathbb N$ (called $d$-NN tree for short) defined as follows. We fix the
torus $\mathbb T^d_n$ of dimension $d$ and area $n$ and equip it with the
metric inherited from the Euclidean metric in $\mathbb R^d$. Then, embed
consecutively $n$ vertices in $\mathbb T^d_n$ uniformly at random and
independently, and let each vertex but the first one connect to its (already
embedded) nearest neighbor. Call the resulting graph $G_n$.
  We show multiple results concerning the degree sequence of $G_n$. First, we
prove that typically the number of vertices of degree at least $k\in \mathbb N$
in the $d$-NN tree decreases exponentially with $k$ and is tightly concentrated
by a new Lipschitz-type concentration inequality that may be of independent
interest. Second, we obtain that the maximum degree of $G_n$ is of logarithmic
order. Third, we give explicit bounds for the number of leaves that are
independent of the dimension and also give estimates for the number of paths of
length two. Moreover, we show that typically the height of a uniformly chosen
vertex in $G_n$ is $(1+o(1))\log n$ and the diameter of $\mathbb T^d_n$ is
$(2e+o(1))\log n$, independently of the dimension.
  Finally, we define a natural infinite analog $G_{\infty}$ of $G_n$ and show
that it corresponds to the local limit of the sequence of finite graphs
$(G_n)_{n \ge 1}$. Moreover, we prove almost surely that $G_{\infty}$ is
locally finite, that the simple random walk on $G_{\infty}$ is recurrent, and
that $G_{\infty}$ is connected.
