Recursion algorithm to generate sitemap

Question

I've got a DataTable containing a sitemap hierarchy with the following columns:

• ItemId
• ParentId
• Name
• Url

I need to generate a set of nested lists in HTML (left the anchor elements out for clarity):

<ul>
<li>Item 1</li>
<li>Item 2</li>
    <ul>
    <li>Sub Item 1</li>
    <li class="current">Sub Item 2</li>
    </ul>
<li>Item 3</li>
</ul>

The tree should only contain branches that lead to the 'current' node/page (so using the above example any child items that Item '1' or '3' have are not displayed. Can anyone help out with some pseudo code / code example that can traverse the tree from the leaf to root building the HTML as it goes? Thanks.

Answer 1

I made something similar, it might not be that efficient but its easy to debug.

1. Find path to selected node.
2. Add rootnodes to list.
3. Find node in list which is in path.
4. Add all childern to this node.
5. Find next node in path.
6. Repeat 4-5 until at selected node, and if not at leaf add selected nodes childern as well.

Alternative: 1. Find selected node, print this and all siblings 2. Print parent and all siblings around the string from 1. 3. Repeat 2 until at root.

Answer 2

This is VBScript, and though I haven't tried to run it, so it may contain errors, it should give you the basic idea.

'# OMITTED: Code to retrieve the record for the current node, and read all info about it.
'# Note: field values are read into variables with the same names.

Dim RootFound
Dim ListHTML
RootFound = false
ListHTML = ""

if ParentID = Null then RootFound = true
ListHTML = "<ul><li>" & Name & "</li></ul>"

while not RootFound
  SQL = "SELECT * FROM DataTable WHERE ItemID = " & ParentID
  '# OMITTED: Code to open dataset using the SQL statement above and 
  'fetch all field values into identically named variables

  ListHTML = "<ul><li>" & Name & "</li>" & ListHTML & "</ul>"
  if ParentID = Null then RootFound = true
wend

Answer 3

Here's some pseudocode. The idea is simple: Start with all the nodes unmarked, and mark your current node's parent, its parent, and so on till you reach the root. By doing this, you'll have marked exactly the nodes on the path from your current node to the root. Then you can simply print all the nodes in another pass, recursing only on "marked" nodes. This is optimal (running time is at most the number of nodes you have to print).

for all n: mark[n]=False
n=current
while n!=root:
    n=parent[n]
    mark[n]=True

def print_tree(n):
    print_node(n)
    if mark[v]==True:
        print '<ul>'
        for each child c of n: print_tree(c)
        print '</ul>'

def print_node(n):
   if n==current: print '<li class="current">' else: print '<li>'
   print name[n]
   print "</li>"

print_tree(root)

parent[n] and name[n] are probably something like n.parent and n.name in your structure. About the "for each child of n" part -- I presume you have an adjacency list maintaining the list of all the children of a given node. (If you don't, then what's the order in which the children should be printed?) In any case, the adjacency lists can be built in time O(number of nodes) by simply adding each node to the "children" list of its parent. The total size of the lists is at most the number of nodes (since each node other than the root occurs in exactly one of the lists) so these lists don't take much memory (a single list might contain a lot of elements, but the total size is bounded).

Answer 4

The more efficient way of doing this if you can change the data structure is using nested sets:

Managing Hierarchical Data in MySQL

Using the Nested Set Data Model for Breadcrumb Links