Nested <ul><li> navigation menu using a recursive Python function

Question

Hi. I want to render this data structure as an unordered list.

menu = [
         [1, 0],
           [2, 1],
           [3, 1],
             [4, 3],
             [5, 3],
               [6, 5],
         [7,1]
        ]

[n][0] is the key
[n][1] references the parent key

The desired output is:

<ul>
<li>Node 1</li>

  <ul>
  <li>Node 2</li>
  <li>Node 3</li>

    <ul>
    <li>Node 4</li>
    <li>Node 5</li>

      <ul>
      <li>Node 6</li>
      </ul>

    </ul>

   <li>Node 7</li>
   </ul>

</ul>

I could probably do this without recursion but that would be no fun. Unfortunately, I am having problems putting it all together. I don't have much experience with recursion and this is proving to be very difficult for me to build and debug.

What is the most efficient way to solve this problem in Python?

Thanks!

Answer 1

def render(nodes, parent = 0):
    if parent not in nodes:
        return
    print('<ul>')
    for n in nodes[parent]:
        print('<li>Node %d</li>' % n)
        render(nodes, n)
    print('</ul>')

Here is the output

>>> nodes = {}
>>> for n in menu:
    if n[1] not in nodes:
        nodes[n[1]] = []
    nodes[n[1]].append(n[0])
>>> render(nodes)
<ul>
<li>Node 1</li>
<ul>
<li>Node 2</li>
<li>Node 3</li>
<ul>
<li>Node 4</li>
<li>Node 5</li>
<ul>
<li>Node 6</li>
</ul>
</ul>
<li>Node 7</li>
</ul>
</ul>

Answer 2

I would not use two-element lists, even if your structure is that simple. Use some TreeNode class, and give it an appropriate __str__ method, e.g.

class TreeNode(object):
    # ...
    # methods for adding children (instances of TreeNode again) etc.

    def __str__(self):
        ret = "<li>%s" % self.value

        if self.children:
            children = "".join([str(c) for c in self.children])
            ret += "<ul>%s</ul>" % children 
        ret += "</li>"

        return ret

... or something like that. Didn't test it, though. Enclose the whole tree's representation in an <ul> tag.