Good idea.But I have some different opinions on time complexity.
Lets look at the Python version from the last fifth row in for statement:
for i in leaves:
j = adj[i].pop()
if len(adj[j]) == 1: newLeaves.append(j)
No matter what data structure set is implemented on can guarantee that both pop and remove operations can be achieved within O(1) .So the time complexity is MORE than O(n).Particularly,for red-black tree implement of set,the time complexity should be O(nlog(n)).
Minimum Height Trees