This is not a complete answer, but there is a nice description of the information in $P_T$ which may prove useful to someone else.

First of all, I will define a slightly different polynomial $\tilde P_Z(T)$: Grafting works the same way, but if $T'$ is the leafing of $T$, then I define $\tilde P_{T'}(z)= z\tilde P_T(z)+1$. It's an easy proof by recursion that $\tilde P_T(z) = P_T(z-1)$, so this new polynomial determines $T$ just as well or poorly as yours.

By "node" of $T$, I mean a vertex of $T$ other than its root, and by "subtree" $T'$ of $T$, I mean a subgraph of $T$, such that for every node of $T$ included in $T'$, the node's parent and the edge to it are also included in $T'$. [Edit: These are non-standard uses of those words.] Then **the coefficient of $z^n$ in $\tilde P_T(z)$ is the number of $n$-node subtrees of $T$.** This is because, for $n>0$, choosing an $n$-node subtree of the leafing of $T$ is the same as choosing an $(n-1)$-node subtree of $T$, and for any $n$, choosing an $n$-node subtree of the grafting of $T$ and $T'$ is the same is choosing a $k$-node subtree of $T$ and an $(n-k)$-node subtree of $T'$ for some $k$ between $0$ and $n$.

Some consequences include:

- If $T$ has $n$ nodes (vertices other than the root), then the highest-order term of $\tilde P_T(z)$ is $z^n$.
- The coefficient of $z$ in $\tilde P_T(z)$ is the degree of the root of $T$.
- If $T$ has $a$ nodes at distance $1$ from the root, and $b$ nodes at distance $2$, then the coefficient of $z^2$ in $\tilde P_T(z)$ is ${a \choose 2}+ b$.
- If $T$ has a total of $n$ nodes, then the coefficient of $z^{n-1}$ is the number of leaves of $T$ (nodes with degree 1).

Hence if $\tilde P_T(z)=\tilde P_{T'}(z)$, then $T$ and $T'$ have the same numbers of vertices and leaves, their roots have the same degrees, and they have the same total number of vertices at distance $2$ from the root. It seems that more should be true, but I haven't proven any more.

**Edit**: I've now proved the following result: if $T$ and $T'$ are graphs whose nodes are distance at most $2$ from the root, and such that $\tilde P_T(z) = \tilde P_{T'}(z)$, then $T\cong T'$.

Proof: A rooted tree of depth at most $2$ corresponds to a sequence of natural numbers $b_1, b_2, \ldots, b_a$, where $a$ is the number of children of the root, and $b_i$ is the number of children of the $i$th child of the root. Then
$$ \tilde P_{T}(z) = \prod_{i=1}^a (z(z+1)^{b_i} + 1)$$ $$ = \prod_{i=1}^a \left(1+{b_i\choose 0}z + {b_i\choose 1}z^2 + \ldots + {b_i\choose k}z^{k+1} + \ldots + {b_i\choose b_i-1}z^{b_i} + {b_i\choose b_i}z^{b_i+1}\right) $$
I show that $\tilde P_T(z)$ determines the $b_i$ up to reordering, and hence $T$ up to isomorphism.

First, note that knowing the $b_i$ up to reordering is the same as knowing the elementary symmetric polynomials in the $b_i$, because they are the solutions of $\prod_{i=1}^a(x-b_i)=0$. Or equivalently, by Newton's identities, that information is contained in the sums $\sum_{i=1}^a b_i^k$ for all $k\geq 0$. In turn, knowing the $\sum_{i=1}^a b_i^k$ for $k$ up to $n$ is the same as knowing the $\sum_{i=1}{b_i\choose k}$ for $k$ up to $n$, through simple linear identities relating the two sets of data.

Now I show that $\tilde P_T(z)$ does determine each $\sum_{i=1}^a {b_i\choose k}$ for $k \geq 0$, by induction on $k$. Suppose we know that $\tilde P_T(z)$ determines $\sum_{i=1}^a {b_i\choose k}$ for $0\leq k < n$, and now consider the coefficient of $z^{n+1}$. There is a contribution from each partition $n+1 = \lambda_1+\lambda_2+\ldots+\lambda_m$ of $n+1$, given by
$$\sum_{i_1,\ldots,i_m\text{ distinct}}\left(\prod_{j=1}^m {b_i\choose \lambda_i-1}z^{\lambda_i}\right)=\left(\sum_{i_1,\ldots,i_m\text{ distinct}}\prod_{j=1}^m {b_i\choose \lambda_i-1}\right)z^{n+1}.$$
Considering the term in parentheses on the right-hand side as a polynomial in the $b_i$, note that it is symmetric in the $b_i$ and has degree $\sum_{j=1}^m(\lambda_j-1) = (n+1)-m< n$ if $m>1$. Hence such contributions are expressible in terms of the $\sum_{i=1}^a {b_i\choose k}$ for $0\leq k < n$, and so can be deduced from $\tilde P_T(z)$ by the induction hypothesis, unless the partition is simply $n+1=(n+1)$, in which case the resulting term is $\sum_{i=1}^a{b_i\choose n}z^{n+1}$. Therefore the coefficient of $z^{n+1}$ in $\tilde P_T(z)$ differs predictably from $\sum_{i=1}^a {b_i\choose n}$, so the latter is deducible from $\tilde P_T(z)$ as well.

Knowing the $\sum_{i=1}^a {b_i\choose k}$ for all $k$, we can work backwards: first we inductively deduce the $\sum_{i=1}^a b_i^k$, from which Newton's identities tell us the values of the elementary symmetric polynomials evaluated at the $b_i$. Then we recover the simplified form of $\prod_{i=1}^a (x-b_i)$, and the $b_i$ are its roots.

**For example:** If $\tilde P_T(z) = z^4 + 3z^3 + 3z^2 + 2z + 1$ and we know $T$ has no nodes of distance more than $2$ from the root, then we can recover $T$ as follows. The coefficient of $z$ is $a=2$, so we are trying to find $b_1$ and $b_2$ such that $$P_T(z) = (z(z+1)^{b_1} + 1)(z(z+1)^{b_2} + 1).$$ The coefficient of $z^2$ is ${a\choose 2} + (b_1+b_2) = 1 + (b_1+b_2) = 3$, so $b_1+b_2 = 2$. And the coefficient of $z^3$ is ${a\choose 3} + \sum_{i\neq j} b_i + \sum_i {b_i\choose 2} = (0) + (b_1+b_2) + \left({b_1\choose 2} + {b_2\choose 2}\right) = 2 + {b_1\choose 2} + {b_2\choose 2} = 3$, so ${b_1\choose 2} + {b_2\choose 2} = 1$. Hence $\frac{b_1^2-b_1}{2} + \frac{b_2^2-b_2}{2} = \frac{(b_1^2 + b_2^2) - (b_1 + b_2)}{2} = \frac{(b_1^2 + b_2^2) - 2}{2} = 1$, so $b_1^2 + b_2^2 = 4$. Therefore $b_1b_2 = \frac{(b_1 + b_2)^2 - (b_1^2 + b_2^2)}{2} = \frac{2^2 - 4}{2} = 0$, so $b_1$ and $b_2$ are the roots of $$x^2 - (b_1+b_2)x + (b_1b_2) = x^2 - 2x.$$ Therefore $b_1$ and $b_2$ are $0$ and $2$, up to reordering, so $T$ is the tree whose root has $a=2$ children, one of which has $0$ children, and the other of which has $2$.

13more comments