²To implement D so that it runs in polynomial time requires a polynomial size data structure for representing the non-empty portion of the tree. This is easily done, and we omit details.