sort an XML file into a tree structure by XSL 1.0

Question

I want to convert an XML file with scattered element to an tree struct XML file.

if the 'identifier' of a menu is exist in another menu's items in input XML file, the menu context should be copied into the 'menu_list' element in output XML file.

Can any one please help me how do I achieve this using XSL1.0.

Input XML file:

<input>
    <menu>
        <identifier>1</identifier>
        <items>
            <item>2</item>
            <item>3</item>
        </items>
    </menu>
    <menu>
        <identifier>2</identifier>
        <items>
            <item>21</item>
            <item>22</item>
        </items>
    </menu>
    <menu>
        <identifier>3</identifier>
        <items>
            <item>31</item>
            <item>32</item>
        </items>
    </menu>
    <menu>
        <identifier>21</identifier>
        <items>
            <item>211</item>
            <item>212</item>
        </items>
    </menu>
    <menu>
        <identifier>22</identifier>
        <items>
            <item>221</item>
            <item>222</item>
        </items>
    </menu>
    <menu>
        <identifier>31</identifier>
        <items>
            <item>311</item>
            <item>312</item>
        </items>
    </menu>
    <menu>
        <identifier>32</identifier>
        <items>
            <item>321</item>
            <item>322</item>
        </items>
    </menu>
</input>

Output XML file:

<input>
    <menu>
        <identifier>1</identifier>
        <items>
            <item>2</item>
            <item>3</item>
        </items>
        <menu_list>
            <menu>
                <identifier>2</identifier>
                <items>
                    <item>21</item>
                    <item>22</item>
                </items>
                <menu_list>
                    <menu>
                        <identifier>21</identifier>
                        <items>
                            <item>211</item>
                            <item>212</item>
                        </items>
                    </menu>
                    <menu>
                        <identifier>22</identifier>
                        <items>
                            <item>221</item>
                            <item>222</item>
                        </items>
                    </menu>
                </menu_list>
            </menu>
            <menu>
                <identifier>3</identifier>
                <items>
                    <item>31</item>
                    <item>32</item>
                </items>
                <menu_list>
                    <menu>
                        <identifier>31</identifier>
                        <items>
                            <item>311</item>
                            <item>312</item>
                        </items>
                    </menu>
                    <menu>
                        <identifier>32</identifier>
                        <items>
                            <item>321</item>
                            <item>322</item>
                        </items>
                    </menu>
                </menu_list>
            </menu>
        </menu_list>
    </menu>
</input>

Answer 1

Try it this way:

XSLT 1.0

<xsl:stylesheet version="1.0" 
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:strip-space elements="*"/>

<xsl:key name="children" match="menu" use="identifier" />
<xsl:key name="parent" match="menu" use="items/item" />

<xsl:template match="/input">
    <xsl:copy>
        <xsl:apply-templates select="menu[not(key('parent', identifier))]"/>
    </xsl:copy>
</xsl:template>

<xsl:template match="menu">
    <xsl:copy>
        <xsl:copy-of select="*"/>
        <xsl:variable name="children" select="key('children', items/item)"/>
        <xsl:if test="$children">
            <menu_list>
                <xsl:apply-templates select="$children"/>
            </menu_list>
        </xsl:if>
    </xsl:copy>
</xsl:template>

</xsl:stylesheet>