Recursion algorithm for creating a sitemap

Here's some pseudocode. The idea is simple: start at all untagged nodes and mark the node's current parent, its parent, etc., until you get to the root. By doing this, you will accurately mark the nodes along the path from the current node to the root. Then you can just print all the nodes in another pass, recursive only on the "marked" nodes. This is optimal (runtime is the maximum number of nodes you should 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]

probably something like n.parent

that n.name

in your structure too. About the "per child n" part - I am assuming that you have an adjacency list containing a list of all children of a given node. (If you don't, what is the order in which the children should be printed?) Either way, adjacency lists can be built in O (number of nodes) time by simply adding each node to the children, the list of its parent. The total size of the lists does not exceed the number of nodes (since each node other than the root occurs in only one of the lists), so these lists do not take up much memory (one list can contain many elements, but the total size is limited).