*First solution.* First we provide a proof that $k \ge n - 1$. Let $T$ be the path where $v_i$ and $v_{i+1}$ are adjacent for all $1 \le i \le n - 1$. Let $\omega$ be a primitive root of unity of order $n$ and let $a_i = \omega^i$ for all $1 \le i \le n$.
If $f(X) = P(X, \omega X)$, then for all $1 \le i \le n-1$ we have $f(\omega^i) = P(a_i, a_{i+1}) = 0$. Since $f(1) = P(a_n, a_1) \ne 0$, $f$ is non-zero and has at least $n-1$ roots. This means that $\deg P \ge \deg f \ge n-1$, proving $k \ge n-1$.

It remains to prove that $k = n - 1$ is sufficient i.e. for any tree $T$ and any $a_1, a_2, \dots, a_n$ we can find a polynomial $P$ of degree at most $n - 1$. For brevity, we call a two-variable polynomial $A(X, Y)$ *symmetric* if $A(X, Y) = A(Y, X)$.
We begin with the following observation. Suppose that $A$ and $B$ are two variable polynomials of degree at most $d$. Then we can find $\alpha \in \mathbb{C}$ such that for any $1 \le i, j \le n$, $A(a_i, a_j) + \alpha B(a_i, a_j) = 0$ if and only if $A(a_i, a_j) = B(a_i, a_j) = 0$. This means that we can "merge" two conditions of degree at most $d$ into a condition of degree at most $d$ (note that this produces a symmetric polynomial if the initial polynomials are symmetric).
For any integer $t \ge 2$, let a *star* of size $t$ be a collection of $t$ edges for which there is a vertex which belongs to all edges. We will prove the following claims.

Claim 1. Let $G$ be a graph with vertices $v_1, v_2, \dots, v_n$ and $E$ edges. Suppose that we can partition the edges of $G$ into a number of stars. Then for any distinct complex numbers $a_1, a_2, \dots, a_n$ we can find a symmetric polynomial $P$ of degree at most $E$ such that for all $1 \le i, j \le n, i \ne j$, $P(a_i, a_j) = 0$ if and only if there is an edge between $v_i$ and $v_j$ in $G$.
*Proof.* We will first prove the claim when $G$ consists of a star of size $E \le n - 1$ and some isolated vertices. Without loss of generality, let $v_1v_2, v_1v_3, \dots, v_1v_{E+1}$ be the edges of $G$. Also let $s_1 = a_1 + a_2, s_2 = a_1 + a_3, \dots, s_E = a_1 + a_{E+1}$.
Consider merging the polynomials $(X - a_1)(Y - a_1)$ and $(X + Y - s_1)(X + Y - s_2) \dots (X + Y - s_E)$ into a polynomial of degree at most $E$ (which is of course symmetric). They both vanish at a pair $a_i, a_j$ if and only if $1 \in \{i, j\}$ and $a_i + a_j \in \{s_1, s_2, \dots, s_E\}$. These two happen if and only if $v_i$ and $v_j$ are adjacent, so this produces a valid polynomial.
For the general case, let $S_1 \cup S_2 \cup \dots \cup S_k$ be the partition of the edges of $G$. For each $1 \le i \le k$, we can find a two variable polynomial $P_i$ of degree at most $|S_i|$ which vanishes only at the edges of $S_i$. Then we can let $P = P_1P_2\dots P_k$, which satisfies the claim as $\deg P \le |S_1| + |S_2| + \dots + |S_k| = E$, as desired.

Claim 2. Any tree $\Gamma$ with odd number of vertices can be partitioned into stars of size 2.
*Proof.* We prove this by induction on the number of the vertices of $\Gamma$. The base case is clear, since $\Gamma$ is a star of size 2 when $\Gamma$ has three vertices.
For the inductive step, let $\Gamma$ be a tree with $2m + 1$ vertices, where $m \ge 2$. Let $u_1u_2\dots u_t$ be a path of maximal length in $\Gamma$ (of course, $t \ge 3$). Then any neighbour of $u_2$ except for maybe $u_3$ must have degree 1, otherwise we can delete $u_1$ and insert two edges, contradicting the maximality of $t$. If $\deg u_2 = 2$, we can form the star $u_1u_2, u_2u_3$ and apply the inductive hypothesis on $\Gamma \setminus \{u_1, u_2\}$. If $\deg u_2 \ge 3$, let $u \neq u_1, u_3$ be a neighbour of $u_2$. Then create the star $u_1u_2, uu_2$ and apply the inductive hypothesis on $\Gamma \setminus \{u, u_1\}$. This proves the claim.

The case where $n$ is odd becomes trivial, since $T$ has $n-1$ edges. Assume that $n$ is even. Without loss of generality, let $\deg v_n = 1$ and let $v_n$ be adjacent to $v_{n-1}$.
Consider the graph $T'$ formed by deleting the edge $v_{n-1}v_n$ from $T$ (but not permuting the $n$ vertices). Clearly, $T'$ consists of $v_n$ and a tree on $v_1, v_2, \dots, v_{n-1}$. As $n-1$ is odd, the edges of $T'$ can be partitioned into stars of size 2 from Claim 2. From Claim 1 it follows that there is a symmetric polynomial $Q(X, Y)$ of degree at most $n-2$ such that $Q(a_i, a_j) = 0$ if and only if $i, j \le n-1$ and $v_i, v_j$ are adjacent in $T$.
Let $g(X)$ be the polynomial of degree $n-1$ such that $g(a_1) = g(a_2) = \dots = g(a_{n-1}) = 0$ and $g(a_n) = -Q(a_{n-1}, a_n) = -Q(a_n, a_{n-1})$. Let $P$ be the polynomial of degree at most $n-1$ obtained by merging $F_1(X, Y) = Q(X, Y) + g(X) + g(Y)$ and $F_2(X, Y) = Q(X, Y)(X+Y-s)$, where $s = a_n + a_{n-1}$. It is easy to see that $P$ vanishes at each $(a_i, a_j)$ for which $v_i, v_j$ are adjacent in $T$.
Suppose that $v_i$ and $v_j$ are not adjacent in $T$. If $i, j \le n-1$, then $F_1(a_i, a_j) = Q(a_i, a_j) \neq 0$. If $n \in \{i, j\}$, then $a_i + a_j \neq s$ and $Q(a_i, a_j) \neq 0$, so $F_2(a_i, a_j) \neq 0$. Hence $P(a_i, a_j) \neq 0$. This proves that $P$ satisfies the required conditions, as desired.

*Second solution.* Establish the lower bound as in Solution 1. We now address the upper bound differently. Let $G$ be a graph on vertices $v_1, \dots, v_n$. Say that a polynomial $P(X, Y)$ is $G$-good if it satisfies the conditions in the statement of the problem. We prove the more general fact below:

Claim. Let $d_i$ be the degree of $v_i$. Assume that these degrees satisfy $d_i \le n-i$ for all $i \le n-1$, and $d_n = 1$. Then there is a $G$-admissible polynomial of degree at most $n-1$.
Notice here that, if $G$ is a tree with vertices ordered so that $d_1 \ge d_2 \ge \dots \ge d_n$, then it satisfies the conditions in the Claim. Indeed, we have $d_n = 1$, and if $d_i > n-i$ for some $i \le n-1$, then we have $2n-2 \sum_{j=1}^n d_j \ge \sum_{j=1}^i (n-i+1) + \sum_{j=i+1}^n 1 = i(n-i+1) + (n-i) = (i+1)(n-i+1) - 1 \ge 2n-1$, which is a contradiction. So, it suffices to prove the Claim.

*Proof of the Claim.* Let
$$P(X, Y) = \sum_{j=0}^{n-1} R_j(Y)X^j$$
be the sought polynomial; set $R_{n-1}(X) = 1$. Denote
$$Q_i(X) = P(X, a_i) = X^{n-1} + \sum_{j=0}^{n-2} q_{ij}X^j, \quad \text{where } q_{ij} = R_j(a_i).$$
So, we will seek for the sequences $C_j = (q_{1j}, q_{2j}, \dots, q_{nj})$ such that there exists a polynomial $R_j$ with $\deg R_j \le n - j - 1$ such that $q_{ij} = R_j(a_i)$. Notice that the first $n-j$ terms of such a sequence determine it uniquely; in particular, there are no restrictions on the sequence $C_0$.
We know that the polynomial $Q_i$ has $d_i$ prescribed roots. For every $i \le n-1$, augment this list by some numbers not from the set $A = \{a_1, a_2, \dots, a_n\}$ to the list $b_{i1}, b_{i2}, \dots, b_{i,n-i}$. Also, denote by $b_{n1}$ the unique prescribed root of $Q_n$. Thus, we should have
$$Q_i(X) = S_i(X) \prod_{j=1}^{\max(n-i, 1)} (X - b_{ij}), \quad (1)$$
where $S_i$ is a monic polynomial with $\deg S_i = i-1$ for $i \le n-1$ and $\deg S_n = n-2$. The only extra conditions we have are that each $S_i$ should achieve non-zero values at the prescribed finite subset $A_i$ of $A$ (containing no prescribed roots of $Q_i$).
The polynomial $Q_1$ is uniquely determined by (1).
Assume that the polynomials $Q_1, \dots, Q_{i-1}$ have already been determined, for some $i \le n-2$. This means that the sequences $S_1, \dots, S_{i-1}$ are also determined. This determines the polynomial $S_i$ up to the constant term. So we may choose this constant term so that $S_i$ has no prohibited roots, thus defining $Q_i$.

*Third solution.* The answer is $n-1$. Use the same argument as Solution 1 for the lower bound.
We can construct such a polynomial via a method that uses no graph theory other than the fact that $T$ has $n-1$ edges.

Lemma 1. Let $k$ be a positive integer and let $A, B \subseteq \mathbb{C}^2$ be two disjoint finite sets. Suppose $|A| = 2k$ and no line intersects $A \cup B$ in more than $k+1$ points. Then there exists a polynomial of degree $k$ that vanishes on $A$ and is non-zero on $B$.
*Proof.* We first argue that we may reduce to the case when $|B| = 1$. This is since if $P$ and $P'$ are polynomials that are zero on $A$ and nonzero on $B$ and $B'$, then a generic linear combination of $P$ and $P'$ is nonzero on $A$ and nonzero on $B \cup B'$. Now suppose $B = \{b\}$.
For $a, a' \in A$, write $a \sim a'$ if $a, a', b$ are collinear. This is an equivalence relation, and each equivalence class has at most $k$ elements. Thus we may pair up the elements of $A$ such that no two paired elements are collinear with $b$. Now let $P$ be the polynomial vanishing on the union of the $k$ lines determined by the pairs, which is nonzero at $b$ by construction.

Lemma 2. Let $a_1, a_2, \dots, a_n$ be distinct complex numbers. Then a line can intersect at most $n$ points of the form $(a_i, a_j)$.
*Proof.* If not, then by the pigeonhole principle such a line must contain two points with the same $x$-coordinate. But then it is vertical and thus can only contain $n$ points.
We are done by applying Lemma 1 with
$$A = \{(a_i, a_j) : v_i v_j \in E(T)\} \quad \text{and} \quad B = \{(a_i, a_j) : i \neq j, v_i v_j \notin E(T)\}.$$