An \(O(n^{2})\) Algorithm for the Characteristic Polynomial of a Tree

We describe an algorithm that uses \( O(n) \) arithmetic operations for computing the determinant of the matrix \( M = (A + \alpha I) \), where \( A \) is the adjacency matrix of an order \( n \) tree. Combining this algorithm with interpolation, we derive a simple algorithm requiring \( O(n^2) \) arithmetic operations to find the characteristic polynomial of the adjacency matrix of any tree. We apply our algorithm and recompute a 22-degree characteristic polynomial, which had been incorrectly reported in the quantum chemistry literature.