1<?xml version="1.0"?>
2<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
3  <xsl:output encoding="utf-8"/>
4  <xsl:template match="node" mode="keep">
5    <node key="{@key}">
6      <xsl:if test="left">
7        <left>
8          <xsl:apply-templates select="left/node" mode="keep"/>
9        </left>
10      </xsl:if>
11      <xsl:if test="right">
12        <right>
13          <xsl:apply-templates select="right/node" mode="keep"/>
14        </right>
15      </xsl:if>
16    </node>
17  </xsl:template>
18
19  <xsl:template match="*"/>
20
21  <xsl:template match="node">
22    <xsl:choose>
23      <xsl:when test="(left and not(right)) or (left/node/@key &lt; right/node/@key)">
24        <node key="{left/node/@key}">
25          <left>
26            <xsl:apply-templates select="left/node"/>
27          </left>
28          <xsl:if test="right">
29            <right>
30              <xsl:apply-templates select="right/node" mode="keep"/>
31            </right>
32          </xsl:if>
33        </node>
34      </xsl:when>
35      <xsl:when test="right">
36        <node key="{right/node/@key}">
37          <xsl:if test="left">
38            <left>
39              <xsl:apply-templates select="left/node" mode="keep"/>
40            </left>
41          </xsl:if>
42          <right>
43            <xsl:apply-templates select="right/node"/>
44          </right>
45        </node>
46      </xsl:when>
47      <xsl:otherwise>
48      </xsl:otherwise>
49    </xsl:choose>
50  </xsl:template>
51
52</xsl:stylesheet>