XSLT Cookbook

Performing a Level-Order Traversal

Problem

You want to order elements by increasing level (tree depth). In other words, you want to traverse the tree breadth first.

Solution

This form of traversal is tailor-made for using xsl:for-each along with xsl:sort:

<xsl:for-each select="//*">
     <xsl:sort select="count(ancestor::*)" data-type="number"/>
     <!--  process the current element -->
</xsl:for-each>

This recursive solution is longer and less obvious:

<xsl:template match="/*"> <xsl:call-template name="level-order"/> </xsl:template> <xsl:template name="level-order"> <xsl:param name="max-level" select="10"/> <xsl:param name="current-level" select="1"/> <xsl:choose> <xsl:when test="$current-depth &lt;= $max-level"> <!-- process the current level --> <xsl:call-template name="level-order-aux"> <xsl:with-param name="level" select="$current-level"/> <xsl:with-param name="actual-level" select="$current-level"/> </xsl:call-template> <!-- process the next level --> <xsl:call-template name="level-order"> <xsl:with-param name="current-level" select="$current-level + 1"/> </xsl:call-template> </xsl:when> </xsl:choose> </xsl:template> <xsl:template name="level-order-aux"> <xsl:param name="level" select="1"/> <xsl:param name="actual-level" select="1"/> <xsl:choose> <xsl:when test="$level = 1"> <!-- Process the current element here --> <!-- $actual-level is the number of the current level --> </xsl:when> <xsl:otherwise> <!-- Recursively descend to the next level on all children --> <xsl:for-each select="*"> ...