## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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="*">
<xsl:call-template name="level-order-aux">
<xsl:with-param name="level"
select="\$level - 1"/>
<xsl:with-param name="actual-level"
select="\$actual-level"/>
</xsl:call-template>
</xsl:for-each>
</xsl:otherwise>
</xsl:choose>
</xsl:template>```

This solution requires that you either set an arbitrary bound for the maximum depth of the tree or compute the max depth. One way of doing so is by finding the node that has no children and more ancestors than any other node without children:

```<xsl:param name="max-level">
<xsl:for-each select="//*[not(*)]">
<xsl:sort select="count(ancestor::*)" data-type="number" order="descending" />
<xsl:if test="position(  ) = 1">
<xsl:value-of select="count(ancestor::*) + 1" />
</xsl:if>
</xsl:for-each>
</xsl:param>```

## Discussion

Arguably, the need to traverse an XML document by level does not arise often. Grouping nodes by depth or distance from the root does not fit into XSLT’s natural control flow, which is organized to express traversals that descend the document tree. This is apparent by the fact that that you had to use `xsl:sort` to coerce the stylesheet to process nodes by their depth or, equivalently, the number of ancestors. The complexity of the recursive solution provides further evidence of this unnatural process.

Still, this form of traversal is sometimes handy. For example, you can use it to process an organizational chart that lists employees by their distance form the top spot, as shown in Example 4-26. The output is shown in Example 4-27.

Example 4-26. Level-order traversal of orgrchart.xml using sort

```<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="text"/>

<xsl:template match="/">
<xsl:for-each select="//employee">
<xsl:sort select="count(ancestor::*)" order="ascending"/>
<xsl:variable name="level" select="count(ancestor::*)"/>
<xsl:choose>
<xsl:when test="\$level = 0">
<xsl:value-of select="@name"/>
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="@name"/>
<xsl:text> has </xsl:text>
<xsl:value-of select="\$level"/>
<xsl:text> boss(es) to knock off.&#xA;</xsl:text>
</xsl:otherwise>
</xsl:choose>
</xsl:for-each>
</xsl:template>

</xsl:stylesheet>```

Example 4-27. Output

```Jil Michel is the head honcho.
Nancy Pratt has 1 boss(es) to knock off.
Jane Doe has 1 boss(es) to knock off.
Mike Rosenbaum has 1 boss(es) to knock off.
Phill McKraken has 2 boss(es) to knock off.
Ima Little has 2 boss(es) to knock off.
Walter H. Potter has 2 boss(es) to knock off.
Wendy B.K. McDonald has 2 boss(es) to knock off.
Cindy Post-Kellog has 2 boss(es) to knock off.
Oscar A. Winner has 2 boss(es) to knock off.
Betsy Ross has 3 boss(es) to knock off.
Craig F. Frye has 3 boss(es) to knock off.
Hardy Hamburg has 3 boss(es) to knock off.
Rich Shaker has 3 boss(es) to knock off.
Allen Bran has 3 boss(es) to knock off.
Frank N. Berry has 3 boss(es) to knock off.
Jack Apple has 3 boss(es) to knock off.
Jack Nickolas has 3 boss(es) to knock off.
Tom Hanks has 3 boss(es) to knock off.
Susan Sarandon has 3 boss(es) to knock off.
R.P. McMurphy has 4 boss(es) to knock off.
Forest Gump has 4 boss(es) to knock off.
Andrew Beckett has 4 boss(es) to knock off.
Helen Prejean has 4 boss(es) to knock off.```

One advantage of the recursive variation is that it is easy to tell when you transition from one level to the next. You could use this information to better format your output, as shown in Example 4-28 and Example 4-29.

Example 4-28. Level-order traversal of orgrchart.xml using recursion

```<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:output method="text" version="1.0" encoding="UTF-8"/>

<xsl:strip-space elements="*"/>

<xsl:template match="/employee">
<xsl:call-template name="level-order"/>
</xsl:template>

<xsl:template name="level-order">
<xsl:param name="max-depth" select="10"/>
<xsl:param name="current-depth" select="0"/>

<xsl:choose>
<xsl:when test="\$current-depth &lt;= \$max-depth">
<xsl:variable name="text">
<xsl:call-template name="level-order-aux">
<xsl:with-param name="level" select="\$current-depth"/>
<xsl:with-param name="actual-level" select="\$current-depth"/>
</xsl:call-template>
</xsl:variable>
<xsl:if test="normalize-space(\$text)">
<xsl:value-of select="\$text"/>
<xsl:text>&#xa;</xsl:text>
<xsl:call-template name="level-order">
<xsl:with-param name="current-depth" select="\$current-depth + 1"/>
</xsl:call-template>
</xsl:if>
</xsl:when>
</xsl:choose>

</xsl:template>

<xsl:template name="level-order-aux">
<xsl:param name="level" select="0"/>
<xsl:param name="actual-level" select="0"/>
<xsl:choose>
<xsl:when test="\$level = 0">
<xsl:choose>
<xsl:when test="\$actual-level = 0">
<xsl:value-of select="@name"/>
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="@name"/>
<xsl:text> has </xsl:text>
<xsl:value-of select="\$actual-level"/>
<xsl:text> boss(es) to knock off.&#xA;</xsl:text>
</xsl:otherwise>
</xsl:choose>
</xsl:when>
<xsl:otherwise>
<xsl:for-each select="employee">
<xsl:call-template name="level-order-aux">
<xsl:with-param name="level" select="\$level - 1"/>
<xsl:with-param name="actual-level" select="\$actual-level"/>
</xsl:call-template>
</xsl:for-each>
</xsl:otherwise>
</xsl:choose>
</xsl:template>

</xsl:stylesheet>```

Example 4-29. Output

```Jil Michel is the head honcho.

Nancy Pratt has 1 boss(es) to knock off.
Jane Doe has 1 boss(es) to knock off.
Mike Rosenbaum has 1 boss(es) to knock off.

Phill McKraken has 2 boss(es) to knock off.
Ima Little has 2 boss(es) to knock off.
Walter H. Potter has 2 boss(es) to knock off.
Wendy B.K. McDonald has 2 boss(es) to knock off.
Cindy Post-Kellog has 2 boss(es) to knock off.
Oscar A. Winner has 2 boss(es) to knock off.

Betsy Ross has 3 boss(es) to knock off.
Craig F. Frye has 3 boss(es) to knock off.
Hardy Hamburg has 3 boss(es) to knock off.
Rich Shaker has 3 boss(es) to knock off.
Allen Bran has 3 boss(es) to knock off.
Frank N. Berry has 3 boss(es) to knock off.
Jack Apple has 3 boss(es) to knock off.
Jack Nickolas has 3 boss(es) to knock off.
Tom Hanks has 3 boss(es) to knock off.
Susan Sarandon has 3 boss(es) to knock off.

R.P. McMurphy has 4 boss(es) to knock off.
Forest Gump has 4 boss(es) to knock off.
Andrew Beckett has 4 boss(es) to knock off.
Helen Prejean has 4 boss(es) to knock off.```

If, for some reason, you wished to have random access to nodes at any specific level, you could define a key as follows:

```<xsl:key name="level" match="employee" use="count(ancestor::*)"/>

<xsl:template match="/">
<xsl:for-each select="key('level',3)">
<!-- do something with the nodes on level 3 -->
</xsl:for-each>
</xsl:template>```

You can also make the match more specific or use a predicate with the key function:

```<xsl:key name="level" match="//employee" use="count(ancestor::*)"/>

<xsl:template match="/">
<xsl:for-each select="key('level',3)[@sex='female']">
<!-- do something with the female employees on level 3 -->
</xsl:for-each>
</xsl:template>```

The use of the XSLT’s key facility is not mandatory because you can always write `select="//*[count(ancestors::*)=3]"` when you need access to level-3 elements; however, performance will suffer if your stylesheet repeatedly evaluates such an expression. In fact, if your stylesheet has a well-defined structure, you’d be much better off explicitly navigating to the desired level, e.g., `select="/employee/employee/employee"`, although this navigation can become quite unwieldy.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required