Here is the complete implementation pattern:
function smallToLargeMerge(n, adj):
subtreeSize = array of size n
// Pass 1: Compute subtree sizes
function computeSize(u, parent):
subtreeSize[u] = 1
for v in adj[u]:
if v != parent:
computeSize(v, u)
subtreeSize[u] = subtreeSize[u] + subtreeSize[v]
// Pass 2: Small-to-large merge
function merge(u, parent, data):
bigChild = -1
for v in adj[u]:
if v != parent:
if bigChild == -1 or subtreeSize[v] > subtreeSize[bigChild]:
bigChild = v
// Process small children first
for v in adj[u]:
if v != parent and v != bigChild:
merge(v, u, newData)
// Merge newData into data
// Process big child last (take its data)
if bigChild != -1:
merge(bigChild, u, data)
// Add current node's contribution
addToData(u, data)
computeSize(root, -1)
merge(root, -1, emptyData)
Time: . Space: .