The k-Tree algorithm [49] is a non-trivial algorithm for the average-case k-SUM problem that has found widespread use in cryptanalysis. Its input consists of k lists, each containing n integers from a range of size m. Wagner’s original heuristic analysis [49] suggested that this algorithm succeeds with constant probability if \(n \approx m^{1/(\log {k}+1)}\) , and that in this case it runs in time O(kn). Subsequent rigorous analysis of the algorithm [33, 39, 47] has shown that it succeeds with high probability if the input list sizes are significantly larger than this. We present a broader rigorous analysis of the k-Tree algorithm, showing upper and lower bounds on its success probability and complexity for any size of the input lists. Our results confirm Wagner’s heuristic conclusions, and also give meaningful bounds for a wide range of list sizes that are not covered by existing analyses. We present analytical bounds that are asymptotically tight, as well as an efficient algorithm that computes (provably correct) bounds for a wide range of concrete parameter settings. We also do the same for the k-Tree algorithm over \(\mathbb {Z}_m\) . Finally, we present extensive empirical evaluation of the k-Tree algorithm and demonstrate the tightness of our results.