# Leaf ordering for hierarchical clustering dendrogram

Assuming merging process was completed and we have the history of n-1 merged clusters (merge two clusters p and q to cluster c = min{p,q}), we are to draw the dendrogram with k leaf nodes (or number of records, whichever is smaller). If k is smaller then number of records then leaves represent cluster objects

I've seen some papers with optimal leaf ordering algorithms that run in O(n^4) time and other fancy algorithms.

I've also heard about "left sliding" ordering.

I'm looking for a simple ordering algorithm to find an admissible ordering of k leaf objects for dendrogram, given history of n-1 merged pairs. Pseudo-code or link would be very nice.

If you read the SLINK publication (an efficient algorithm for single-link clustering; using $O(n)$ memory and $O(n^2)$ time, as opposed to the $O(n^3)$ standard algorithm), then you will find that it is based on what is called a "pointer representation". This representation allows rather efficient construction of a non-overlapping dendrogram. Should be in $O(n)$, if you have this representation.