Of course a list is just a boring tree
That's true, although if a designer wanted to display a custom navigation element based on a context list they might be interested in ensuring that the data isn't a tree if the display code didn't know how to display a tree.
I agree that navigation menus would probably be best generated in the master template. I think we have identified one distinguishing characteristic in the service contracts of navigation elements; namely whether or not the caller can supplement the generated data with additional specific data.
I think in general having a small selection of navigation element service contracts which guarantee the data structure returned, for which the content could be generated in different, commonly used ways is a really useful idea.
