Good question -- so the most pathological tree of n nodes would be one with depth of O(n). If this was the case, the closure table would be of size O(n^2). In t

Good question -- so the most pathological tree of n nodes would be one with depth of O(n). If this was the case, the closure table would be of size O(n^2). In tree applications I can think of--like an org chart or site comments--the depth is O(log(n)), in which case the closure table is just O(n). Note that this same kind of pathological tree would be hell for a recursive query too, just trading space for time.