On 11/04/2012, at 4:23 PM, Arnaud Bailly wrote:
You are right, of course. By "sensible properties" I simply meant the list of (Path, Value) is assumed to represent a tree (eg. it has been generated by a traversal of some original tree). By "ordered" I meant Path(s) segments are lexicographically ordered and (Path, Value) are enumerated from a tree using depth-first traversal.
My main point was that there is a "sensible property" that you did not mention, and you still have not mentioned it, namely that *ALL* non-structural information about a node must be represented in the Value that corresponds to it (and of course, that all the nodes are actually listed somewhere). Given your constraints, the sequence of (Path,Value) pairs must begin with a ([],Value) representing the non-structural information about the root, then a sequence of (1:x11,v11) ... (1:x1k,v1k) .... (n:xn1,vn1) ... (n:xnm,vnm) pairs which you partition as <(x11,v11) ... (x1k,v1k)> ... <(xn1,vn1) ... (xnm,vnm)> and then process recursively to make the children. The initial lexicographic ordering is _not_ an important property because you can ensure that by sorting. As long as the paths are numbered correctly, the kind of traversal that was used to generate the initial list is not important either. But the no-missing-nodes and no-missing-non-structural- information properties are crucial.